Ищите отсортированную 2D матрицу [дубликат]
3 ответа
init: m [1..n (строки), 1 .... m (столбцы)]
i = n, j = 1
Начать с (i, j):
STEP 1) if the value equals m(i,j) return (i,j)
STEP 2) if the value > m(i,j) go to step 1 with j+=1
STEP 3) else go to step 1 with i-=1
в каждый шаг, если j или i выходит за рамки, не возвращает решения.
Сложность этого решения составляет O (n + m), в случае n = m сложность равна O (n)
Интересно, есть ли решение log (n * m), как в бинарном поиске
ИЗМЕНИТЬ другое возможное решение:
STEP 1)take the middle (n/2,m/2) of the matrix and compare it to the value
STEP 2) if the value equals m(i,j) return (i,j)
STEP 3) if the value is higher you can get rid from the first quarter
STEP 4) if the value is lower you can get rid from the forth quarter
STEP 5) split the 3 other quarters to 2, a rectangle and a box,
send those both items to step 1 in a recursive manner
Я не уверен в эффективности этого решения: если R = N * M, то T (R) = T (R / 2) + T (R / 4) + O (1)
Я просто открыл блокнот и немного написал, но я думаю, что это будет сделано за время O(x), где x - больший индекс между n и m. Худшим случаем для этого алгоритма будет, если искомый термин будет равен самому большому термину в массиве, для чего этот метод будет циклически повторяться n или m (в зависимости от того, что больше) раз. Если это будет встречаться часто, можно просто начинать снизу справа, а не сверху слева, и декрементировать признаки, а не инкрементировать их.
int[] SearchArray(int s, int[][] array)
{
int i = 0;
int j = 0;
int n = array.GetLength(0);
int m = array.GetLength(1);
if (s > array[n][m])
return null;
while (i < n && j < m)
{
if (array[i][j] > s)
return null;
if (array[i][j] == s)
return new int[]{i,j};
try
{
if (array[i+1][j+1] < s)
{
i++;
j++;
}
else if (array[i+1][j] > array[i][j+1])
if (array[i+1][j] < s)
i++;
else
j++;
else if (array[i][j+1] > array[i+1][j])
if (array[i][j+1] < s)
j++;
else
i++;
else if (array[i+1][j] == array[i][j+1])
if (n < m)
i++;
else
j++;
}
catch(IndexOutOfRangeException e)
{
if (i == n-1)
j++;
if (k == m-1)
i++;
}
}
}
Отредактировано для оптимизации и форматирования
Допустим, у нас есть
1 2 5 7
2 4 7 9
3 5 8 9
5 6 9 9
Теперь мы ищем 6. Вы можете видеть, что есть «полоса», идущая от верхнего правого (5 7) до нижнего левого (5 6 7), где значения меньше 6 переходят в значения больше 6 («полоса» отмечена *):
1 2 5*7
2 4*7 9
3 5*8 9
5*6*9 9
Таким образом, алгоритм будет:
- проверить, больше ли верхний левый, чем ваше число -> return null
- проверить, меньше ли нижний правый, как ваше число - > return null
- пройдите по диагонали от верхнего левого угла до нижнего правого, пока не найдете «полосу»
- , следуйте по полосе в обоих направлениях, пока не найдете номер.