b*****t
发帖数: 296 | 1 请教一个面试题：
给定行列分别排序的矩阵，如何有序的输出所有元素：
比如：
1 2 2 25
1 2 4 26
1 2 4 30
1 3 100 101
输出：
1 1 1 1 2 2 2 2 3 4 4 25 26 30 100 101 |
b*****t
发帖数: 296 | |
g*******s
发帖数: 2963 | |
r**h
发帖数: 1288 | 4 O(nm)是lower bound了吧？
请问一下O(nm)算法的思路是什么？
我能想到的是，假设矩阵大小是n*m，那么取m、n中较小的那个（假设是m）做m way
merge，时间复杂度是O(mn log m)
【在 b*****t 的大作中提到】
: 俺只知道一个O(nm)的算法。
|
l***8
发帖数: 149 | 5 I don't think O(nm) is possible. O(nm log(min(n,m)) is probably the best you
can do.
Consider the special case of a square nxn matrix, where elements along the
diagonal line A[0][k],A[1][k-1],A[2][k-2]...,A[k][0] have very small
differences in their values, yet are randomly ordered. By solving the 2D
sorting problem, you've effectively sorted every such diagnoal line. |
u*****o
发帖数: 1224 | 6 我觉得是不是可以把POINTER放在左上角，就是第一个数1那里。然后不断比较1的右边
（2）还有1的下面(1)哪个大，小的那个（1）挪到它的右边或下面（第三行的的1），
再和大的数（2）比较。。。这样遍历一遍应该就可以的吧？ |
k*******t
发帖数: 144 | 7
如果是下面的matrix，貌似这个方法就不work啦。
[[1, 1, 2, 7],
[1, 2, 3, 8],
[2, 3, 5, 9],
[2, 5, 5, 10]]
当pointer一个指向3 (matrix[2][1]), 另一个指向 7（matrix[0][3]), 走下去会发现
3(matrix[1][2])会打印到5后面。
【在 u*****o 的大作中提到】
: 我觉得是不是可以把POINTER放在左上角，就是第一个数1那里。然后不断比较1的右边
: （2）还有1的下面(1)哪个大，小的那个（1）挪到它的右边或下面（第三行的的1），
: 再和大的数（2）比较。。。这样遍历一遍应该就可以的吧？
|
s*****r
发帖数: 43070 | 8 priority queue，先放(1,1),然后开始pop，每pop出一个，把其右边和下面的数放入
queue，如果queue里面已经有了，就不放 |
s*******e
发帖数: 1630 | 9 不对吧，pop了一个之后就加入了两个，然后从两个之中选小的pop，queue里边还有一
个，但这时候应该又加入两个吧，新加入的两个未必比剩余那个大啊
【在 s*****r 的大作中提到】
: priority queue，先放(1,1),然后开始pop，每pop出一个，把其右边和下面的数放入
: queue，如果queue里面已经有了，就不放
|
r*********n
发帖数: 4553 | 10 i agree. i don't think O(nm) is possible. this problem is similar to the
rank/selection problem for a 2-D matrix.
you
【在 l***8 的大作中提到】
: I don't think O(nm) is possible. O(nm log(min(n,m)) is probably the best you
: can do.
: Consider the special case of a square nxn matrix, where elements along the
: diagonal line A[0][k],A[1][k-1],A[2][k-2]...,A[k][0] have very small
: differences in their values, yet are randomly ordered. By solving the 2D
: sorting problem, you've effectively sorted every such diagnoal line.
|
|
|
s*****r
发帖数: 43070 | 11 priority queue，这题就是个变形的BFS
【在 s*******e 的大作中提到】
: 不对吧，pop了一个之后就加入了两个，然后从两个之中选小的pop，queue里边还有一
: 个，但这时候应该又加入两个吧，新加入的两个未必比剩余那个大啊
|
u****0
发帖数: 155 | 12 用HashMap, O(mn) time, O(mn) space in worst case. |
c******a
发帖数: 789 | 13 这个的时间复杂度是O(mn lgk), k是priority queue heap的高度吧。
要知道queue里已经放了没有，最简单的办法是一个m x n的boolean2维数组，空间复杂
度O(mn)。不知道我理解对了没。。
不过我最喜欢这个解法，简单易懂。
【在 s*****r 的大作中提到】
: priority queue，这题就是个变形的BFS
|
m*******i
发帖数: 34 | 14 为什么不能用merge sort， 是O(mn)吧？
望指正。 |
b****g
发帖数: 192 | 15 赞同，用BFS再加上一个heap保存当前最小值，就是O（mn lgk）。
BFS就是从左上角开始，bfs相同的值，一旦不同就终止此分支，把这个不同的值打入
min-heap。下次bfs从这个min-heap所存的最小值开始。
如此循环。
K最大就是m+n吧？没仔细想。
【在 c******a 的大作中提到】
: 这个的时间复杂度是O(mn lgk), k是priority queue heap的高度吧。
: 要知道queue里已经放了没有，最简单的办法是一个m x n的boolean2维数组，空间复杂
: 度O(mn)。不知道我理解对了没。。
: 不过我最喜欢这个解法，简单易懂。
|
g*******s
发帖数: 2963 | 16 同问
【在 m*******i 的大作中提到】
: 为什么不能用merge sort， 是O(mn)吧？
: 望指正。
|
u*****o
发帖数: 1224 | 17 MERGE SORT是指把原来的MATRIX分成两半，每一个是2*4的ARRAY， 然后MERGE两个
ARRAY是吗？
这样的话应该没问题吧 |
p****3
发帖数: 448 | 18 我是这么想的(假设n x n)
左上角肯定是最小值
右下角肯定是最大
那么每个包含的小矩阵也是最小值在左上角
选了[0][0]后有两个小矩阵的左上角是可能的下一个最小值
以此类推最多从n个数中选下一个最小值
最坏情况O(n^2 lgn)
但从n个数中选下一个最小值的情况很少出现(只有一次)
我猜还是O(n^2) |
q*********3
发帖数: 470 | 19 不一定非要分两个array吧，把它看成个变形的merge sort，直接四个array也可以
merge啊，而且这题还有个使问题简化的信息，这个matrix是行和列都排好序的
【在 u*****o 的大作中提到】
: MERGE SORT是指把原来的MATRIX分成两半，每一个是2*4的ARRAY， 然后MERGE两个
: ARRAY是吗？
: 这样的话应该没问题吧
|
z****e
发帖数: 54598 | 20 新拿到的value可能出现在你作为cache的结构的任意一个位置
这样插入这个value就多了一次查找，所以是O(mn ln(min(m,n)))
【在 m*******i 的大作中提到】
: 为什么不能用merge sort， 是O(mn)吧？
: 望指正。
|
u*****o
发帖数: 1224 | 21 如果是MERGE 4个ARRAY的话就不能是o(mn)了吧。。虽然列也是排好的，但不能简化
COMPLEXITY，因为无法确定同一个数的右面和下面谁大，这样的话应该是mn(log(mn))
吧。。。
其实MERGE 2个ARRAY也是一样的。。我觉得用MERGE SORT只能达到mn(log(mn))。。
应该有更好的办法啊，因为给出的条件（行列都排好序）并没有充分利用啊。。
【在 q*********3 的大作中提到】
: 不一定非要分两个array吧，把它看成个变形的merge sort，直接四个array也可以
: merge啊，而且这题还有个使问题简化的信息，这个matrix是行和列都排好序的
|
