Монотонно увеличивающийся 2-й массив

Question

Дайте алгоритм для поиска заданного элемента x (укажите координаты) в матрице n на n, где строки и столбцы монотонно растут.

Мои мысли: Уменьшите размер проблемного набора.

В 1-м столбце найдите самый большой элемент <= x. Мы знаем, что х должен быть в этом ряду или после (ниже). В последнем столбце матрицы найдите наименьший элемент> = x. Мы знаем, что х должен быть в этом ряду или раньше. Сделайте то же самое с первой и последней строками матрицы. Теперь мы определили подматрицу таким образом, чтобы, если x вообще был в матрице, он находился в этой подматрице. Теперь повторите алгоритм на этой подматрице ... Что-то в этом роде.

[YAAQ: еще один вопрос о массивах.]

Answer 1

Я думаю, вы не можете надеяться на более чем O(N), что достижимо. (N - ширина матрицы).

Почему вы не можете надеяться на большее

Представьте себе такую ​​матрицу:

0 0 0 0 0 0 ... 0 0 x
0 0 0 0 0 0 ... 0 x 2
0 0 0 0 0 0 ... x 2 2
.....................
0 0 0 0 0 x ... 2 2 2
0 0 0 0 x 2 ... 2 2 2
0 0 0 x 2 2 ... 2 2 2
0 0 x 2 2 2 ... 2 2 2
0 x 2 2 2 2 ... 2 2 2
x 2 2 2 2 2 ... 2 2 2

где x - неизвестное число (не то же самое число, т. Е. Оно может быть разным в каждом столбце). Чтобы удовлетворить монотонность матрицы, вы можете разместить любое из 0, 1 или 2 во всех x местах. Итак, чтобы узнать, есть ли в матрице 1, вам нужно проверить все x мест, а их N.

Как это сделать O(n)

Представьте, что вы должны найти указатели первого столбца с number > q (заданным числом) для всех строк. Вы начинаете в верхнем правом углу матрицы; если число, которое вы видите, больше, вы идете налево; иначе идти вниз. Конец, когда вы находитесь в последнем ряду. Точки, куда вы спустились, - это места, которые вы ищете. Если у любого из них есть номер, который вы ищете, вы его нашли.

Этот алгоритм O(n), потому что на каждом шаге вы либо идете влево или вниз. В целом, он не может идти больше N раз влево и N раз вниз. Поэтому это O(n).

Answer 2

Выберите угловой элемент, самый большой в своем ряду и самый маленький в своем столбце (или другой способ). Сравните с х. В зависимости от результата сравнения вы можете исключить строку или столбец из дальнейшего поиска.

Новая матрица имеет сумму измерений, уменьшенную на 1, по сравнению с исходной. Примените вышеизложенное итеративно. После 2*n шагов вы получите матрицу 1x1.

Answer 3

Если «количество строк и столбцов монотонно увеличивается» означает, что значения в каждом (row, col) увеличиваются так, что для любой строки (rowM, col1) <(rowM, col2) <... <(rowM, colN) <(rowM + 1, col1) ... </p>

Затем вы можете просто обработать его как одномерный массив, отсортированный от наименьшего к наибольшему, и выполнить стандартный двоичный поиск, выбрав элемент, равный 1/2 (строки * столбцы) с начала, а затем сэмплировать элемент, который на 1/4 (строки * столбцы) находится позади (если первый выбранный элемент> x) или вперед (если первый выбранный элемент