b*t
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
给定行列分别排序的矩阵，如何有序的输出所有元素：
比如：
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
2 楼
俺只知道一个O(nm)的算法。
g*s
3 楼
O(nm)就是线性了吧？
r*h
4 楼
O(nm)是lower bound了吧？
请问一下O(nm)算法的思路是什么？
我能想到的是，假设矩阵大小是n*m，那么取m、n中较小的那个（假设是m）做m way
merge，时间复杂度是O(mn log m)
【在 b*****t 的大作中提到】
: 俺只知道一个O(nm)的算法。
请问一下O(nm)算法的思路是什么？
我能想到的是，假设矩阵大小是n*m，那么取m、n中较小的那个（假设是m）做m way
merge，时间复杂度是O(mn log m)
【在 b*****t 的大作中提到】
: 俺只知道一个O(nm)的算法。
l*8
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.
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
6 楼
我觉得是不是可以把POINTER放在左上角，就是第一个数1那里。然后不断比较1的右边
（2）还有1的下面(1)哪个大，小的那个（1）挪到它的右边或下面（第三行的的1），
再和大的数（2）比较。。。这样遍历一遍应该就可以的吧？
（2）还有1的下面(1)哪个大，小的那个（1）挪到它的右边或下面（第三行的的1），
再和大的数（2）比较。。。这样遍历一遍应该就可以的吧？
k*t
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
8 楼
priority queue，先放(1,1),然后开始pop，每pop出一个，把其右边和下面的数放入
queue，如果queue里面已经有了，就不放
queue，如果queue里面已经有了，就不放
s*e
9 楼
不对吧，pop了一个之后就加入了两个，然后从两个之中选小的pop，queue里边还有一
个，但这时候应该又加入两个吧，新加入的两个未必比剩余那个大啊
【在 s*****r 的大作中提到】
: priority queue，先放(1,1),然后开始pop，每pop出一个，把其右边和下面的数放入
: queue，如果queue里面已经有了，就不放
个，但这时候应该又加入两个吧，新加入的两个未必比剩余那个大啊
【在 s*****r 的大作中提到】
: priority queue，先放(1,1),然后开始pop，每pop出一个，把其右边和下面的数放入
: queue，如果queue里面已经有了，就不放
r*n
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.
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
11 楼
priority queue，这题就是个变形的BFS
【在 s*******e 的大作中提到】
: 不对吧，pop了一个之后就加入了两个，然后从两个之中选小的pop，queue里边还有一
: 个，但这时候应该又加入两个吧，新加入的两个未必比剩余那个大啊
【在 s*******e 的大作中提到】
: 不对吧，pop了一个之后就加入了两个，然后从两个之中选小的pop，queue里边还有一
: 个，但这时候应该又加入两个吧，新加入的两个未必比剩余那个大啊
u*0
12 楼
用HashMap, O(mn) time, O(mn) space in worst case.
c*a
13 楼
这个的时间复杂度是O(mn lgk), k是priority queue heap的高度吧。
要知道queue里已经放了没有，最简单的办法是一个m x n的boolean2维数组，空间复杂
度O(mn)。不知道我理解对了没。。
不过我最喜欢这个解法，简单易懂。
【在 s*****r 的大作中提到】
: priority queue，这题就是个变形的BFS
要知道queue里已经放了没有，最简单的办法是一个m x n的boolean2维数组，空间复杂
度O(mn)。不知道我理解对了没。。
不过我最喜欢这个解法，简单易懂。
【在 s*****r 的大作中提到】
: priority queue，这题就是个变形的BFS
m*i
14 楼
为什么不能用merge sort， 是O(mn)吧？
望指正。
望指正。
b*g
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)。不知道我理解对了没。。
: 不过我最喜欢这个解法，简单易懂。
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
16 楼
同问
【在 m*******i 的大作中提到】
: 为什么不能用merge sort， 是O(mn)吧？
: 望指正。
【在 m*******i 的大作中提到】
: 为什么不能用merge sort， 是O(mn)吧？
: 望指正。
u*o
17 楼
MERGE SORT是指把原来的MATRIX分成两半，每一个是2*4的ARRAY， 然后MERGE两个
ARRAY是吗？
这样的话应该没问题吧
ARRAY是吗？
这样的话应该没问题吧
p*3
18 楼
我是这么想的(假设n x n)
左上角肯定是最小值
右下角肯定是最大
那么每个包含的小矩阵也是最小值在左上角
选了[0][0]后有两个小矩阵的左上角是可能的下一个最小值
以此类推最多从n个数中选下一个最小值
最坏情况O(n^2 lgn)
但从n个数中选下一个最小值的情况很少出现(只有一次)
我猜还是O(n^2)
左上角肯定是最小值
右下角肯定是最大
那么每个包含的小矩阵也是最小值在左上角
选了[0][0]后有两个小矩阵的左上角是可能的下一个最小值
以此类推最多从n个数中选下一个最小值
最坏情况O(n^2 lgn)
但从n个数中选下一个最小值的情况很少出现(只有一次)
我猜还是O(n^2)
q*3
19 楼
不一定非要分两个array吧，把它看成个变形的merge sort，直接四个array也可以
merge啊，而且这题还有个使问题简化的信息，这个matrix是行和列都排好序的
【在 u*****o 的大作中提到】
: MERGE SORT是指把原来的MATRIX分成两半，每一个是2*4的ARRAY， 然后MERGE两个
: ARRAY是吗？
: 这样的话应该没问题吧
merge啊，而且这题还有个使问题简化的信息，这个matrix是行和列都排好序的
【在 u*****o 的大作中提到】
: MERGE SORT是指把原来的MATRIX分成两半，每一个是2*4的ARRAY， 然后MERGE两个
: ARRAY是吗？
: 这样的话应该没问题吧
z*e
20 楼
新拿到的value可能出现在你作为cache的结构的任意一个位置
这样插入这个value就多了一次查找，所以是O(mn ln(min(m,n)))
【在 m*******i 的大作中提到】
: 为什么不能用merge sort， 是O(mn)吧？
: 望指正。
这样插入这个value就多了一次查找，所以是O(mn ln(min(m,n)))
【在 m*******i 的大作中提到】
: 为什么不能用merge sort， 是O(mn)吧？
: 望指正。
u*o
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是行和列都排好序的
COMPLEXITY，因为无法确定同一个数的右面和下面谁大，这样的话应该是mn(log(mn))
吧。。。
其实MERGE 2个ARRAY也是一样的。。我觉得用MERGE SORT只能达到mn(log(mn))。。
应该有更好的办法啊，因为给出的条件（行列都排好序）并没有充分利用啊。。
【在 q*********3 的大作中提到】
: 不一定非要分两个array吧，把它看成个变形的merge sort，直接四个array也可以
: merge啊，而且这题还有个使问题简化的信息，这个matrix是行和列都排好序的
相关阅读
onsite 归来，求祝福！微软的certificate对找工作有用吗这是positive sign么？面试时遇到见过的题是痛快的给解还是假装犹豫一下Houston税前7万的工作税后有多少呢？NYC有啥software engineer的公司呢？今天接到一个recruiter的电话菜鸟提问勿拍：找内推比网上直接申请好很多吗？问个C++的问题conference call能用手机打吗？以后别说L在NYC没分部了3sum on LeetCode OJ有人讨论去startup的么A第一轮电面，求建议，面完必update请各位推荐机械材料方面的大公司问G家一题，SDETentry level software engineerInterview street上的一题求助求本书 Cracking Coding Interviews,请问bloomberg