sortingmatrix的selectalgorithm

这是一个谷歌面试问题：

给定N * Nmatrix。 所有的行都被sorting，所有的列都被sorting。 findmatrix的第K个最大元素。

在n ^ 2中做它很简单，我们可以使用堆或合并sorting（n lg n），然后得到它，但有没有更好的方法，比（n lg n）好？

数组的示例::

1 5 7 12 3 6 8 14 4 9 10 15 11 17 19 20 

1 <5 <7 <12和1 <3 <4 <11与其他行和列相似。 现在说我们需要find第十个最小的元素，在这里它是11 ..希望这增加了一些细节问题…

Answer 1

是的，由于Frederickson和Johnson有一个O（K）algorithm。

Greg N. Frederickson和Donald B. Johnson。 广义select和sorting：sortingmatrix 。 SIAM J. Comput。 13，pp。14-30。 http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no

Answer 2

用例子中给出的matrix：如果要search第7个元素，则知道第7个元素在元素M [4] [1..4]，M [1..4] [ 4]。 你得到两个已经sorting的数组，12,14,15,20和11,17,19可以合并。 然后你应用二进制search是O（log N）。

推广：对于这个matrix中第k个最大的元素，你必须select适当的层：[2N-1] + [2（N-1）-1] + …> = k，所以select合适的algorithm层为了Sum [2（Ni）-1]> = k，对于i = 0，N-1，其中i是层的编号。 find我之后，图层号码，你将有数组中的2（Ni）-1元素，必须合并，然后search。 search该层的复杂度是O（log [2（Ni）-1] = O（log（Ni））…

算术级数导致

0> = I ^ 2-2 * N * I + K

i1,2 = N + -sqrt（N ^ 2-k），其中k是我们search的元素。

Answer 3

由于所有东西都已经sorting了，你可以做一个对angular线search。 （虽然坦率地说，我不知道“所有的行都被sorting了，所有的列都被sorting了”是什么意思，如果这是真的，那么就去matrix的对angular枚举中的第k个元素。

Answer 4

顺时针旋转matrix45度。 你会得到一个菱形的数据集。 高度将是2N-1，从顶部的每一行中的元素的数目将如下：1,2,3,4,5,4,3,2,1对于N = 5

你会发现连续的每个数字总是大于上面的任何数字。

对于第k行（从1开始计数），对于k <N，您将具有k个元素，对于k> = N k，2N-k属于{1..2N-1}

通过计算从第1行到第k-1行和第1行到第k行的元素的累积数量，可以find目标所在的行（sum（1到k-1）

现在，你已经find了最坏情况N总数的一行元素。 你可以sorting他们，然后find正确的。 这个取O（N ln N）

由于N = sqrt（n），该algorithm的总体成本为O（sqrt（n）ln（sqrt（n）））

Answer 5

基于N，您可以find元素所在的对angular线。 例如在matrix中，

  1 5 7 12 3 6 8 14 4 9 10 15 11 17 19 20 

您可以通过确定以前对angular线中的元素总数来推断对angular线，

 /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 / 

我们需要find对angular线的原因是因为上面的对angular线将总是具有比任何当前对angular线元素更小的元素，并且下面的对angular线总是具有比任何当前对angular线元素都大的元素。

所以，你可以肯定，对angular线d4具有所需的元素（因为它包含第七大到第十大）。 由于直到前一个对angular线有6个元素，你只需要在对angular线d4find第四个最大的元素。

Answer 6

你先从（0,0）开始search一下。 （0,0）的2个孩子（0,1）和（1,0）被添加到第二元素的潜在候选者列表中。 循环挑选潜在候选人列表中的最小元素作为下一个元素，将其添加到潜在候选人列表中。 find第k个元素时停下来。

使潜在的候选人名单一分钟堆。 堆永远不会比n + m大。

如果k大于n * m / 2，也可以从最后一个元素（n，m）做相反的处理。

最坏情况：这将是n * m / 2 lg（n + m），而不是n * m lg（n * m）的sorting。

Answer 7

你可以在时间O（n log n）中find第k ^个最小元素，如果你注意到：

1. 生成一个位于Array [i] [j]和Array [k] [l]之间的随机数，使得Array [i] [j] <Array [k] [l]需要O（n）

使用[1]作为子程序，可以使用类似于RANDOMIZED-SELECT的程序在整个数组中生成第k ^个最小的数字。

Answer 8

我的代码是O（k）algorithm。 它不适用于某个边缘情况（可能每个方向都有一个：x和y）。 我列出了边缘情况，所以有人可以修复它。 我不打算解决这个问题，因为这对我来说是睡觉的时间。

algorithm总结：只需跟踪两个可能最小的候选＃，一个在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); 

Answer 9

以下是我的C ++解决scheme，它基于最小堆。 当matrix中的某个单元格位于最小堆的顶部时，右侧和/或下侧的数字将被插入到堆中。

 #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; }