Feb. 29th, 2012

the_grue: (Default)
Условия: дана матрица (для простоты скажем, что она квадратная) n*n с произвольными числами (необязательно целыми). Все строки отсортированы слева направо, а столбцы - сверху вниз. Требуется дать алгоритм по нахождению k-го (0<=k<n^2) по величине элемента матрицы.

Эта задача уже когда-то всплывала, но давно и не у меня (в оригинале взята с интервью). Не знаю, чего ожидали на интервью, но у этой задачи есть весьма нетривиальное, магическое решение - сложностью O(n). Для сравнения, лучшее простое решение, которое мне известно, требует O(k*log(n)) времени, т.е. O(n^2 * log(n)) для k порядка n^2. Я тогда долго над ним медитировал, но интуитивно так и не понял (может быть потому, что там рассматривалась более сложная задача, втч матрицы могли иметь "пустые" ячейки). А пару дней назад прошелся по нему снова и - наконец - понял, что центральная идея - это просто рекурсивное разбиение массива. И вот стало мне интересно: сможет ли кто-нибудь из моих френдов найти то самое магическое решение своими силами (а не через гугл, хехе) с этими подсказками:
1. вам пригодятся подматрицы из предыдущего поста
2. алгоритм поиска k-го элемента в одномерном массиве за линейное время



В качестве мотивации для такой задачи, пример ее применения: даны отсортированные массивы чисел A и B, |A|=|B|=n. Найти k-й по величине элемент массива ci,j, определенного так: ci,j := bj - ai.

Чтобы свести задачу (2) к описанной задаче (1), вместо массива "c" будем работать с массивом di,j := bj - an-i-1. В этом массиве все строки и столбцы отсортированы, что и требуется условиями задачи (1).

Например:
A=1,2,3,4   B=-3,2,6,8

A\B|  -3  2  6  8
-----------------
4  |  -7 -2  2  4
3  |  -6 -1  3  5
2  |  -5  0  4  6
1  |  -4  1  5  7


Следовательно, если мы можем решить задачу нахождения k-го элемента произвольной матрицы за время O(n), то можем решить и эту за время O(n). Самая прекрасная деталь здесь состоит в том, что для решения задачи (2) не надо даже строить промежуточный массив из n^2 элементов: вместо этого мы можем работать с такой имплементацией класса Matrix, которая просто эмулирует массив, а на самом деле ее at(i,j) возвращает b(j)-a(n-i-1), size() возвращает (n,n), итд. В итоге мы можем решить задачу (2) целиком за линейное время!

Если кому-то это интересно (и если никто меня не опередит), напишу потом развернутое оптимальное решение этой задачи.
Page generated Sep. 19th, 2017 07:01 pm
Powered by Dreamwidth Studios