Это вопрос интервью с Google:
Учитывая матрицу N * N. Все строки отсортированы, и все столбцы отсортированы. Найти Kth Наибольший элемент матрицы.
делает это в n ^ 2 просто, и мы можем сортировать его с помощью кучи или сортировки слияния (n lg n), а затем получить его, но есть ли лучший подход, лучше, чем (n lg n)?
пример массива::
1 5 7 12
3 6 8 14
4 9 10 15
11 17 19 20
1 < 5 < 12 < 3 < 4 < 4 аналогично другим строкам и столбцам. теперь скажем, что нам нужно найти 10-й наименьший элемент, здесь 11. Надеюсь, это добавит некоторые детали к вопросу...
Да, есть алгоритм O (K) из-за Фредериксона и Джонсона.
Грег Н. Фредериксон и Дональд Б. Джонсон. Обобщенный выбор и ранжирование: отсортированные матрицы. SIAM J. Comput. 13, с. 14-30. http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no
С матрицей, приведенной в примере: Если вы хотите найти 7-й элемент, вы знаете, что 7-й элемент находится в элементах M [4] [1..4], M [1..4] [4]. Вы получаете уже отсортированные массивы, 12,14,15,20 и 11,17,19, которые можно объединить. Затем вы применяете двоичный поиск, который является O (log N).
Обобщите: для k-го самого большого элемента в этой матрице вам нужно выбрать правильный уровень: [2N-1] + [2 (N-1) -1] +... >= k, поэтому алгоритм выберите правильный слой для поиска - Sum [2 (Ni) -1] >= k, для я = 0, N-1, где я - номер слоя. После того, как вы найдете i, номер слоя, у вас будет 2 (N-i) -1 элемента в этом массиве, которые необходимо объединить, а затем выполнить поиск. Сложность поиска этого уровня - O (log [2 (N-i) -1] = O (log (N-i))...
Арифметическая прогрессия приводит к
0 >= я ^ 2-2 * N * + К
i1,2 = N + -sqrt (N ^ 2-k), где k - элемент, который мы ищем...
Поскольку все уже отсортировано, вы можете просто выполнить диагональный поиск. (Хотя, честно говоря, я не знаю, что это означает, что "все строки отсортированы и все столбцы отсортированы". Если это правда буквально, то просто перейдите к k-му элементу в диагональном перечислении матрицы.)
вращать матрицу по часовой стрелке на 45 градусов. Вы получите набор данных в форме алмаза. Высота будет 2N-1, количество элементов в каждой строке сверху будет выглядеть следующим образом: 1,2,3,4,5,4,3,2,1 для N = 5
Вы узнаете, что каждое число в строке всегда больше любого числа выше.
для k-й строки (считая от 1), у вас будет k элементов для k < N и 2N-k при k >= N k принадлежит {1..2N-1}
Вычисляя накопительное число элементов из строк 1 в k-1 и от 1 до k, вы найдете строку, в которой находится ваша цель (сумма (от 1 до k-1)
Теперь, когда вы обнаружили ряд элементов с наихудшим итогом N всего. Вы можете отсортировать их, а затем найти правильный. это taks O (N ln N)
так как N = sqrt (n), общая стоимость этого алгоритма равна O (sqrt (n) ln (sqrt (n)))
На основе N вы можете найти диагональ, где находится элемент. Например, в матрице
1 5 7 12
3 6 8 14
4 9 10 15
11 17 19 20
Вы можете вывести диагональ, определив общее количество элементов в предыдущих диагоналях,
/diagonal#/elements/# of elements/cumulative # of elements/
/d1/ 1 / 1 / 1 /
/d2/ 3 5 / 2 / 1+2 = 3 /
/d3/ 4 6 7 / 3 / 1+2+3 = 6 /
/d4/ 11 9 8 12 / 4 / 1+2+3+4 = 10 /
/d5/ 17 10 14 / 3 /
/d6/ 19 15 / 2 /
/d7/ 20 / 1 /
Причина, по которой нам нужно найти диагональ, состоит в том, что вышеприведенные диагонали всегда будут содержать элементы, меньшие, чем любой из существующих диагональных элементов, а внизу диагоналей всегда будут элементы, большие, чем любой из существующих диагональных элементов.
Итак, вы можете быть уверены, что диагональ d4 имеет необходимый элемент (поскольку он содержит 7-е место по величине до 10-го по величине). Поскольку до предыдущей диагонали было 6 элементов, вам просто нужно найти 4-й по величине элемент в диагонали d4.
Сначала вы начинаете поиск дыхания, начиная с (0,0). (0,0) s 2 ребенка (0,1) и (1,0) добавляются в список потенциальных кандидатов для 2-го элемента. Петля, выбирающая наименьший элемент в списке потенциальных кандидатов, будет следующим элементом, добавьте его детей в список потенциальных кандидатов. Остановитесь, когда найдете k-ый элемент.
Сделайте потенциальными кандидатами список минутной кучи. Куча никогда не будет больше, чем n + m.
Также вы можете сделать обратное от последнего элемента (n, m), если k больше n * m/2.
Худший случай: это будет n * m/2 lg (n + m) вместо n * m lg (n * m) сортировки.
Вы можете найти наименьший элемент k th во времени O (n log n), если вы заметили, что:
Используя [1] в качестве подпрограммы, вы можете использовать процедуру, похожую на RANDOMIZED-SELECT, чтобы генерировать наименьшее число k th во всем массиве.
Мой код ниже - это алгоритм O (k). Он не работает на определенном краевом случае (вероятно, по одному в каждом направлении: x и y). Я перечислил кромку, чтобы кто-то мог ее исправить. Я не собираюсь это исправлять, потому что это время для меня.
Резюме алгоритма: вам нужно только отслеживать два кандидата #, которые могут быть самыми маленькими, один при продолжении в направлении x и один, продолжая в направлении y. Подумайте об этом, и это может иметь смысл для вас.
enum Direction {
X,
Y
};
struct Index
{
Index(int unsigned x, int unsigned y)
: x(x),
y(y)
{}
void operator = (Index const & rhs)
{
x = rhs.x;
y = rhs.y;
}
int unsigned x;
int unsigned y;
};
int unsigned solve(int unsigned i_k, int unsigned ** i_data, int unsigned i_n)
{
if (1 == i_k) {
return i_data[0][0];
}
Direction dir = X;
Index smaller(0,0);
Index larger(0,0);
if (i_data[1][0] < i_data[0][1]) {
dir = X;
smaller = Index(1,0);
larger = Index(0,1); }
else {
dir = Y;
smaller = Index(0,1);
larger = Index(1,0);
}
for (int unsigned i = 0; i < (i_k - 2); ++i) {
int unsigned const x = smaller.x;
int unsigned const y = smaller.y;
if (X == dir) {
if ((x + 1) == i_n) {
// End of row
smaller = larger;
larger.x += 1;
dir = Y; }
else if (i_data[x + 1][y] < i_data[larger.x][larger.y]) {
smaller.x += 1; }
else {
smaller = larger;
larger = Index(x + 1, y);
dir = Y;
} }
else {
if ((y + 1) == i_n) {
// End of col
smaller = larger;
larger.y += 1;
dir = X; }
else if (i_data[x][y + 1] < i_data[larger.x][larger.y]) {
smaller.y += 1; }
else {
smaller = larger;
larger = Index(x, y + 1);
dir = X;
}
}
}
return i_data[smaller.x][smaller.y];
}
не работает в следующем краевом случае (где мы попадаем в конец строки). Я буду спать, не стесняйтесь исправить этот случай:
size = 4;
data = createMatrix(size);
data[0][0] = 1; data[1][0] = 6; data[2][0] = 10; data[3][0] = 11;
data[0][1] = 3; data[1][1] = 7; data[2][1] = 12; data[3][1] = 14;
data[0][2] = 4; data[1][2] = 8; data[2][2] = 13; data[3][2] = 15;
data[0][3] = 5; data[1][3] = 9; data[2][3] = 19; data[3][3] = 20;
answer = solve(14, data, size);
assertAnswer(answer, 15, ++testNum);
deleteMatrix(data, size);
Ниже приведено мое решение на С++, основанное на минимальной куче. Когда ячейка в матрице находится сверху верхней части кучи, число справа и/или нижняя сторона будет вставлена в кучу.
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
struct Entry {
int value;
int x;
int y;
bool operator < (const Entry& other) {
return this->value > other.value;
}
};
bool getKthNumber(int* matrix, int row, int col, int k, int* result){
if(matrix == NULL || row <= 0 || col <= 0 || result == NULL)
return false;
if(k <= 0 || k > row * col)
return false;
vector<Entry> minHeap;
Entry first = {matrix[0], 0, 0};
minHeap.push_back(first);
make_heap(minHeap.begin(), minHeap.end());
for(int i = 0; i < k; ++i){
first = minHeap[0];
int x = first.x;
int y = first.y;
if(first.y == 0 && first.x < row - 1){
Entry next = {matrix[(x + 1) * col], x + 1, y};
minHeap.push_back(next);
push_heap(minHeap.begin(), minHeap.end());
}
if(first.y < col - 1){
Entry next = {matrix[x * col + y + 1], x, y + 1};
minHeap.push_back(next);
push_heap(minHeap.begin(), minHeap.end());
}
pop_heap(minHeap.begin(), minHeap.end());
minHeap.pop_back();
}
*result = first.value;
return true;
}