Полностью отсортированная матрица

Question

Этот вопрос мне задавали в одном из моих собеседований -

M - это двумерная матрица размером n на n, в которой сортируются каждая строка и каждый столбец, а все элементы матрицы различны. Мне нужен алгоритм O (n) - учитывая индексы i, j, i0, j0 в качестве входных данных, вычислить количество элементов M, меньших, чем M [i, j] и больших, чем M [i0, j0]. Я пробовал разные подходы для этого, но не мог понять. Помощь будет принята с благодарностью. Следующая часть состояла в том, чтобы узнать медиану M в ожидаемом времени O (nlogn).

Answer 1

Рассмотрим матрицу как набор строк.В каждой строке есть индексы самых маленьких и самых больших допустимых значений.Если вам известны эти индексы, вы можете вычислить количество допустимых значений в этой строке в O (1).(Под действительным я подразумеваю значение между M [i, j] и M [i0, j0].)

Теперь матрица отсортирована.Давайте возьмем нижнюю границу: (i, j).

• Если вы хотите найти индекс наименьшего действительного значения в предыдущей строке, он должен находиться справа от (i, к).Это потому, что прямо над (i, j) должно быть недопустимое (слишком маленькое) значение.

• Если вы хотите найти индекс наименьшего допустимого значения в следующей строке, он имеетлежать с левой стороны (i, j) (или справа под ним).

Таким образом, вам нужно пройти не более 2n «шагов» по ​​матрице, чтобы найти индексы нижней границыкаждого ряда.То же самое с верхней границей.Таким образом, ваша ходьба - O (n), тогда вычисление количества допустимых значений для каждой строки - O (n), поэтому общее время - O (n).

Используя этот алгоритм, можно решить срединную проблему,Во-первых, обратите внимание, что если вы вычисляете решение предыдущей задачи, вы можете выбрать допустимое значение случайным образом за линейное время, используя индексы для граничных значений в каждой строке.Медиана может быть затем рассчитана с помощью алгоритма деления пополам:

selection_find(M, i0,j0, i2,j2, K):
    # Find K-th smallest number between M(i0,j0) and M(i2,j2)
    # assumption: M(i0,j0)<M(i2,j2)
    N := number of values between M(i0,j0) and M(i2,j2)
    # assumption: k<N
    Pick at random i1,j1 so that M(i0,j0)<M(i1,j1)<M(i2,j2)
    L := number of values between M(i0,j0) and M(i1,j1)
    if L==K:
        The answer is M(i1,j1)
    if L<K:
        The answer is selection_find(M, i1,j1, i2,j2, K-L)
    if L>K:
        The answer is selection_find(M, i0,j0, i1,j1, K)

median_find(M):
    The answer is selection_find(M, 1,1, n,n, n²/2)

Каждый шаг занимает O (N).Будет O (log N²) = O (2log N) = O (log N) шагов (каждый шаг должен вдвое уменьшать количество рассматриваемых значений).Следовательно, общая сложность равна O (NlogN).