T家一题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

T家一题

T家一题# JobHunting - 待字闺中

f*m2012-12-08 08:12

1 楼

Given a matrix with all elements sorted on each individual row and column
find the K-th smallest one.
我能想到的：
Merge sort N个或者M个sorted arrays,（M和N为matrix大小），直到merge结果包括K
个元素，复杂度为K*min(M, N)。
但好像没有很好利用行、列都sort这个性质，大家有何更好的方法？

c*a2012-12-08 08:12

2 楼

只想到heap。。。这解法不好.

r*m2012-12-08 08:12

3 楼

类似二分法
i = m/2
j = n/2
while (i> 0 && j > 0 && i < m-1 && j < n-1) {
if (k > i*j && k < (i+1)*(j+1)) {
mergeSearch(matrix[i][0...j], matrix[0...i][j], k - (i*j));
} else if (k < i * j) {
i = i/2;
j = j/2;
} else {
i = (i+m)/2;
j = (j+n)/2;
}
}

l*a2012-12-08 08:12

4 楼

去学习一下杨氏矩阵

K

【在 f*********m 的大作中提到】

: Given a matrix with all elements sorted on each individual row and column
: find the K-th smallest one.
: 我能想到的：
: Merge sort N个或者M个sorted arrays,（M和N为matrix大小），直到merge结果包括K
: 个元素，复杂度为K*min(M, N)。
: 但好像没有很好利用行、列都sort这个性质，大家有何更好的方法？

f*m2012-12-08 08:12

5 楼

学习了，多谢：）

【在 l*****a 的大作中提到】

: 去学习一下杨氏矩阵
:
: K

n*w2012-12-08 08:12

6 楼

Searching a 2D Sorted Matrix
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix.html

K

【在 f*********m 的大作中提到】

f*m2012-12-08 08:12

7 楼

这题和search可能还有差别。

【在 n*******w 的大作中提到】

: Searching a 2D Sorted Matrix
: http://www.leetcode.com/2010/10/searching-2d-sorted-matrix.html
:
: K

c*a2012-12-08 08:12

8 楼

区别很大....

【在 f*********m 的大作中提到】

: 这题和search可能还有差别。

A*e2012-12-08 08:12

9 楼

搜到一个wwwyhx大牛的帖子：
http://www.1point3acres.com/bbs/thread-13146-1-1.html

p*22012-12-08 08:12

10 楼

哪里说了是杨氏矩阵？

【在 l*****a 的大作中提到】

: 去学习一下杨氏矩阵
:
: K

p*22012-12-08 08:12

11 楼

哪里说了是杨氏矩阵？

【在 l*****a 的大作中提到】

: 去学习一下杨氏矩阵
:
: K

l*a2012-12-08 08:12

12 楼

Given a matrix with all elements sorted on each individual row and column
这个条件不是吗？

【在 p*****2 的大作中提到】

:
: 哪里说了是杨氏矩阵？

p*22012-12-08 08:12

13 楼

还真没看过。刚才以为是杨辉三角了。

【在 l*****a 的大作中提到】

: Given a matrix with all elements sorted on each individual row and column
: 这个条件不是吗？

l*o2012-12-08 08:12

14 楼

re.
敢问wwwyhx大牛在这个版上么？

【在 A****e 的大作中提到】

: 搜到一个wwwyhx大牛的帖子：
: http://www.1point3acres.com/bbs/thread-13146-1-1.html

A*e2012-12-08 08:12

15 楼

在呀，头像都是一样的。
他在别的帖子里也说过，这道题太难，可以不管

【在 l****o 的大作中提到】

: re.
: 敢问wwwyhx大牛在这个版上么？

a*e2012-12-08 08:12

16 楼

我的想法：
第一个一定是（1，1）
第二个是（1,2)或（2，1）
如果第二个是（1，2），那么第三个是(1,3),或（2，1）
K每增加1，只需要在”刚才try过的但没有被选用的元素以及刚选中元素的2个neighbor
中的一个“这
样一个集合寻找。
这样brute force的方法大约是O(k**2).如果heap应该是O(max(M,N)+K*lg(K))。

A*e2012-12-08 08:12

17 楼

第三个为什么不能是(1,2)或(2,1)?

【在 a**********e 的大作中提到】

: 我的想法：
: 第一个一定是（1，1）
: 第二个是（1,2)或（2，1）
: 如果第二个是（1，2），那么第三个是(1,3),或（2，1）
: K每增加1，只需要在”刚才try过的但没有被选用的元素以及刚选中元素的2个neighbor
: 中的一个“这
: 样一个集合寻找。
: 这样brute force的方法大约是O(k**2).如果heap应该是O(max(M,N)+K*lg(K))。

d*g2012-12-08 08:12

18 楼

这个算法的复杂度不一定比用堆好吧？“给定任意一个数，有办法判断该元素是矩阵中
第几大的”，这一步应该是O(n)，n是矩阵的max{长，宽}，然后二分法找到恰好大于k
个数的数是O(lgm)，其中m是矩阵中的最大值减最小值的大小。所以总复杂度是O(n*lgm
)。而用堆的复杂度是O(k*lgn)。不知道我的理解对么？

【在 A****e 的大作中提到】

: 搜到一个wwwyhx大牛的帖子：
: http://www.1point3acres.com/bbs/thread-13146-1-1.html

a*e2012-12-08 08:12

19 楼

粗心了。谢谢指出，已纠正。

【在 A****e 的大作中提到】

: 第三个为什么不能是(1,2)或(2,1)?

l*o2012-12-08 08:12

20 楼

求教堆的解法

k
lgm

【在 d*********g 的大作中提到】

:
: 这个算法的复杂度不一定比用堆好吧？“给定任意一个数，有办法判断该元素是矩阵中
: 第几大的”，这一步应该是O(n)，n是矩阵的max{长，宽}，然后二分法找到恰好大于k
: 个数的数是O(lgm)，其中m是矩阵中的最大值减最小值的大小。所以总复杂度是O(n*lgm
: )。而用堆的复杂度是O(k*lgn)。不知道我的理解对么？

d*g2012-12-08 08:12

21 楼

假设矩阵为L行H列，显然最小元素一定在第一行里（实际上就是
matrix[0][0]）。那么把第一行的元素放到min_heap里，做成一个有H个元素的堆。容
易得到最小元素。
最小元素在第0列上，于是删掉堆里的最小元素，并且把第0列的下一个元素放进堆里。
原因是第二小的元素一定在第0列的下一个元素以及堆里之前的第一行剩下元素当中。
于是这样又在堆里得到了第二小的元素。假设这个元素是在第i列里。于是删掉这个堆
里的最小元素，并把第i列的下一个元素放到堆里，理由和上面类似。
这样的操作进行k次就行了。建堆的时间是O(H)，k次插入堆的操作是O(k*lgH)。于是总
复杂度是O(H+k*lgH)。
求牛人看看这算法对不

【在 l****o 的大作中提到】

: 求教堆的解法
:
: k
: lgm

l*o2012-12-08 08:12

22 楼

多谢。但我不太明白。
用第一行建完堆，然后用第一列的元素，从上到下依次插入堆吗？

【在 d*********g 的大作中提到】

: 假设矩阵为L行H列，显然最小元素一定在第一行里（实际上就是
: matrix[0][0]）。那么把第一行的元素放到min_heap里，做成一个有H个元素的堆。容
: 易得到最小元素。
: 最小元素在第0列上，于是删掉堆里的最小元素，并且把第0列的下一个元素放进堆里。
: 原因是第二小的元素一定在第0列的下一个元素以及堆里之前的第一行剩下元素当中。
: 于是这样又在堆里得到了第二小的元素。假设这个元素是在第i列里。于是删掉这个堆
: 里的最小元素，并把第i列的下一个元素放到堆里，理由和上面类似。
: 这样的操作进行k次就行了。建堆的时间是O(H)，k次插入堆的操作是O(k*lgH)。于是总
: 复杂度是O(H+k*lgH)。
: 求牛人看看这算法对不

d*g2012-12-08 08:12

23 楼

比如这么个矩阵：
1 4 8
2 6 10
5 7 11
首先把 1 4 8 放到堆里，然后发现第0列的元素1是最小的，于是把1拿出堆，把第0列
的下一个元素放到堆里，也就是2.
现在堆里有 2 4 8，然后发现第0列的元素2是最小的，接着把2拿出堆，把第0列的下一
个元素放到堆里，也就是5.
现在堆里有 5 4 8. 发现第1列的元素4是最小的，把4拿出堆，把第1列的下一个元素放
到堆里，也就是6.
现在堆里有5 6 8. 以此类推。

【在 l****o 的大作中提到】

: 多谢。但我不太明白。
: 用第一行建完堆，然后用第一列的元素，从上到下依次插入堆吗？

l*o2012-12-08 08:12

24 楼

I am still not sure how this solution works. But I think your analysis of
the complexity might not be correct. For example, if k = 4, the correct
answer might be element [1][1] (index starting from 0). This solution will
go over the first column before checking [1][1] (?) Then the complexity in
this case is O(column length * \log(row length)).
On the other hand, this solution's worst case complexity is greater than O(
number of element/2), when k = median (?)

【在 d*********g 的大作中提到】

:
: 比如这么个矩阵：
: 1 4 8
: 2 6 10
: 5 7 11
: 首先把 1 4 8 放到堆里，然后发现第0列的元素1是最小的，于是把1拿出堆，把第0列
: 的下一个元素放到堆里，也就是2.
: 现在堆里有 2 4 8，然后发现第0列的元素2是最小的，接着把2拿出堆，把第0列的下一
: 个元素放到堆里，也就是5.
: 现在堆里有 5 4 8. 发现第1列的元素4是最小的，把4拿出堆，把第1列的下一个元素放

m*k2012-12-08 08:12

25 楼

你的回复里感觉有几处不清楚和错误的地方。
1. “Then the complexity in this case is O(column length * \log(row length))“
假设ColumnLength=m, RowLength=n, 你说的复杂度就是m*log(n)，这其实比堆解法的
复杂度k*log(n)快得多，因为k可以等于n*m/2. 堆解法的复杂度worst case是O(n*m*
log(n)).
2. "this solution's worst case complexity is greater than O(m*n/2)"
这不是很显然的么: O(k*log(n)) = O(n*m*log(n)) > O(M*n).
>>>总结一下：
1. 堆解法，复杂度是k*log(n), worst case (k=m*n/2, median)时，复杂度为O(m*n*
log(n))
2. 间接二分法，复杂度是O(n*log(max-min)). 具体方法是：
(1) 求一个整数x在矩阵中第几大，O(n)
(2) 在[a, b]范围的整数内，找出一个整数y，使其为第k+1大。这里二分a到b的范围
，需要O(log(b-a))步。每步需要调用(1)，综合时间是 O(n*log(b-a)). 这里a是矩阵
的min，b是矩阵max.
(3) 找到y后，在矩阵中找小于y的元素中的最大值，时间O(n).
所以综合时间为O(n*log(max-min)). (1)和(2)具体怎么做，可以参考”搜索杨氏矩阵
“。

【在 l****o 的大作中提到】

: I am still not sure how this solution works. But I think your analysis of
: the complexity might not be correct. For example, if k = 4, the correct
: answer might be element [1][1] (index starting from 0). This solution will
: go over the first column before checking [1][1] (?) Then the complexity in
: this case is O(column length * \log(row length)).
: On the other hand, this solution's worst case complexity is greater than O(
: number of element/2), when k = median (?)

l*o2012-12-08 08:12

26 楼

??我说的有错么？我一开始的意思就是说他之前的结论是有问题的阿，和你总结的是一
个意思啊.....

))“

【在 m***k 的大作中提到】

: 你的回复里感觉有几处不清楚和错误的地方。
: 1. “Then the complexity in this case is O(column length * \log(row length))“
: 假设ColumnLength=m, RowLength=n, 你说的复杂度就是m*log(n)，这其实比堆解法的
: 复杂度k*log(n)快得多，因为k可以等于n*m/2. 堆解法的复杂度worst case是O(n*m*
: log(n)).
: 2. "this solution's worst case complexity is greater than O(m*n/2)"
: 这不是很显然的么: O(k*log(n)) = O(n*m*log(n)) > O(M*n).
: >>>总结一下：
: 1. 堆解法，复杂度是k*log(n), worst case (k=m*n/2, median)时，复杂度为O(m*n*
: log(n))

d*g2012-12-08 08:12

27 楼

首先，当k=4的时候，正确答案不应该是第[2][0]个元素么？还是说你的k是从0开始取
的？如果k从0开始取的，那k=4的时候正确答案是第[1][1]个元素。那么这个时候需要
做5次堆操作，也就是O((k+1)*log(row length))。为了方便，认为k是从1开始取的吧
，也就是说k=1时需要找最小的元素。这个时候取第k个元素的复杂度是O(k*log(row
length)).
你给的O(column length * \log(row length)) 没有一般性吧？取第k个元素与是否遍
历某一列没有必然联系。
当k是median的时候，自然复杂度就是O(mn/2 * log(row length))了，但是这不妨碍
O(k*log(row length)) 的正确性啊，因为这时k就等于 mn/2。所以说取得第k个元素
的复杂度是O(k*log(row length))没有问题吧？这个复杂度的逻辑其实很好想啊，要取
第k个元素，就要进行k次堆操作；每进行一次对操作就要log(row length)的时间。

【在 l****o 的大作中提到】

l*o2012-12-08 08:12

28 楼

嗯，median只是想说明有些情况堆解法不好用，不同的k可能有不同的better solution
不过我还是没懂这个算法，你方便写一下伪代码么？多谢~

【在 d*********g 的大作中提到】

:
: 首先，当k=4的时候，正确答案不应该是第[2][0]个元素么？还是说你的k是从0开始取
: 的？如果k从0开始取的，那k=4的时候正确答案是第[1][1]个元素。那么这个时候需要
: 做5次堆操作，也就是O((k+1)*log(row length))。为了方便，认为k是从1开始取的吧
: ，也就是说k=1时需要找最小的元素。这个时候取第k个元素的复杂度是O(k*log(row
: length)).
: 你给的O(column length * \log(row length)) 没有一般性吧？取第k个元素与是否遍
: 历某一列没有必然联系。
: 当k是median的时候，自然复杂度就是O(mn/2 * log(row length))了，但是这不妨碍
: O(k*log(row length)) 的正确性啊，因为这时k就等于 mn/2。所以说取得第k个元素