g*****u
发帖数: 298 | 1 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
O(mn) | D*C
发帖数: 97 | 2 感觉是应该先根据k的值先确定落在哪条逆对角线上，然后在这条斜线上搜索
【在 g*****u 的大作中提到】
: 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
: O(mn)
| r****o
发帖数: 1950 | 3 同问。
还有一道题是对这个matrix排序，用什么算法最好?
【在 g*****u 的大作中提到】
: 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
: O(mn)
| j***n
发帖数: 301 | 4 既然每行都排好序了，用归并怎么样？
【在 r****o 的大作中提到】
: 同问。
: 还有一道题是对这个matrix排序，用什么算法最好?
| D***h
发帖数: 183 | 5 简单归并不行，时间上为O(n^3).
【在 j***n 的大作中提到】
: 既然每行都排好序了，用归并怎么样？
| j***n
发帖数: 301 | 6 哦，复杂度是有点儿高，不过应该是O(n^2 * lg(n))吧
【在 D***h 的大作中提到】
: 简单归并不行，时间上为O(n^3).
| f*k
发帖数: 95 | | b******n
发帖数: 823 | | r**********1
发帖数: 292 | 9 呵呵，我想到点啥。【i,j】表示第 i row, 第 j column.我们给定m*n矩阵。
如果找最1个最大数，那就是最右下角【m,n】的数了；第2个最大数，就是min([m,n-1]
called A,[m-1,n] called B);
现在假设A给选中了。我们继续找第3个,就是min([m,n-2] called C,B); 注意，我们不
用比较【m-1,n-1】和[m-1,n]（B），理由是同一行的右面的大。
如果我们假设B给选中了，我们继续找第3个，就是min(A,[m-2,n]);注意，我们不用比
较[m-1,n-1]和[m,n-1],理由就是同一列的下面的大。
规律就是从右下角开始顺着最下或最右两条边开始找，然后次最右或此最下,这样来找
那个k个最大的值。
我们访问每个元素仅一次，复杂度O(m*n)啦。
唉，不容易啊。好不容易发挥了一把。明天我面试，希望有如此发挥了。。。。。。 | j***n
发帖数: 301 | 10 没看懂
0 0 96
0 98 99
96 99 100
找第4大？
1]
【在 r**********1 的大作中提到】
: 呵呵，我想到点啥。【i,j】表示第 i row, 第 j column.我们给定m*n矩阵。
: 如果找最1个最大数，那就是最右下角【m,n】的数了；第2个最大数，就是min([m,n-1]
: called A,[m-1,n] called B);
: 现在假设A给选中了。我们继续找第3个,就是min([m,n-2] called C,B); 注意，我们不
: 用比较【m-1,n-1】和[m-1,n]（B），理由是同一行的右面的大。
: 如果我们假设B给选中了，我们继续找第3个，就是min(A,[m-2,n]);注意，我们不用比
: 较[m-1,n-1]和[m,n-1],理由就是同一列的下面的大。
: 规律就是从右下角开始顺着最下或最右两条边开始找，然后次最右或此最下,这样来找
: 那个k个最大的值。
: 我们访问每个元素仅一次，复杂度O(m*n)啦。
| | | T**********n
发帖数: 480 | | b**f
发帖数: 20 | 12 It looks like, those papers are talking about a more general problem.
a[i][j]
In our case,
a[i][j]
【在 T**********n 的大作中提到】
: http://www.springerlink.com/content/ph106337753883w3/
: http://www.math.tau.ac.il/~nogaa/PDFS/mono.pdf
: 这事到现在好像还没个定论呢
: 另外楼主问的是最坏复杂度还是平均复杂度？
| r**********1
发帖数: 292 | 13 谢谢提醒，我的算法有问题。
【在 j***n 的大作中提到】
: 没看懂
: 0 0 96
: 0 98 99
: 96 99 100
: 找第4大？
:
: 1]
| j**l
发帖数: 2911 | 14 老杨，又见老杨。这是个著名的杨氏矩阵(Young Tableau), 集堆和BST的特性于一身。 | j**l
发帖数: 2911 | | x******3
发帖数: 245 | 16 每个节点中保存子树大小
【在 j**l 的大作中提到】
: 先解决如何在BST找第K大，肯定有启发。
| c***p
发帖数: 221 | 17 在young tableaux中找第K大元素可以参考在heap中找第k大元素，因为young tableaux
和heap有些类似.
while (count
e = table.remove_min();
table.youngify(); //去掉最小元素后，调整结构以保持young tabuleaux特性，
count++;
}
return e;
youngify()与heapify()类似，通过shift元素来保持young tabuleaux特性， 其实现
可参考
http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf
for a table (m, n), youngify() 的复杂度：at most (m+n)
【在 g*****u 的大作中提到】
: 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
: O(mn)
| b******v
发帖数: 1493 | 18 thanks!
tableaux
【在 c***p 的大作中提到】
: 在young tableaux中找第K大元素可以参考在heap中找第k大元素，因为young tableaux
: 和heap有些类似.
: while (count : e = table.remove_min();
: table.youngify(); //去掉最小元素后，调整结构以保持young tabuleaux特性，
: count++;
: }
: return e;
: youngify()与heapify()类似，通过shift元素来保持young tabuleaux特性， 其实现
: 可参考
| s******9
发帖数: 84 | 19 应该是 O(n*lgn)吧。
【在 j***n 的大作中提到】
: 哦，复杂度是有点儿高，不过应该是O(n^2 * lg(n))吧
| s******9
发帖数: 84 | 20 时间复杂度是O(n*lg(min(m,n))). 空间复杂度是O(min(m,n)). | | | w******0
发帖数: 43 | 21 How about selection algorithm?
for random N size , array, find kth big number will only take O(N)
for matrix, it only has mn size, so take O(MN)
【在 g*****u 的大作中提到】
: 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
: O(mn)
| c*******n
发帖数: 112 | 22 if extra memory is allowed, why not use external sorting. The complexity
would be O(k * min(n, m)) | g*****u
发帖数: 298 | 23 你怎么做？如果二分查找，剩下的两块丧失了young matrix的特性。
用每次取出一个最小的方法，需要O(mn(m+n))超过了O(mn)的要求。
用merge sort需要O(mn log(min(m,n)),也超过了，还要用extra mem。
【在 x******3 的大作中提到】
: 每个节点中保存子树大小
| i**********b
发帖数: 77 | 24 my approach:
given integer K, matrix A, 找出K的所有factor pairs whose product is K E.g:
K = 100
factor pairs:
(i, j)[] = (1, 100), (2, 50), (4, 25), (5, 20), (10, 10).
找A[i,j] and A[j, i]中最小的一个 | b******v
发帖数: 1493 | 25 如果8x8矩阵里找第13大的数，就只找(1,13)和(13,1)吗？
【在 i**********b 的大作中提到】
: my approach:
: given integer K, matrix A, 找出K的所有factor pairs whose product is K E.g:
: K = 100
: factor pairs:
: (i, j)[] = (1, 100), (2, 50), (4, 25), (5, 20), (10, 10).
: 找A[i,j] and A[j, i]中最小的一个
| m*****g
发帖数: 226 | 26 这样就是O(k*(m+n))的复杂度了
tableaux
【在 c***p 的大作中提到】
: 在young tableaux中找第K大元素可以参考在heap中找第k大元素，因为young tableaux
: 和heap有些类似.
: while (count : e = table.remove_min();
: table.youngify(); //去掉最小元素后，调整结构以保持young tabuleaux特性，
: count++;
: }
: return e;
: youngify()与heapify()类似，通过shift元素来保持young tabuleaux特性， 其实现
: 可参考
|
|
