谷歌电面，被三哥黑了

假定是M行N列，可以用O（M*N*Log(M)）的时间复杂度做，然后需要额外空间复杂度是O（M*N）的2D matrix来存结果。
想要O（M）的空间应该也可以，但是需要在远矩阵里进行swap，code感觉蛮难写的。
感觉楼主只要不是一上来把矩阵从头到位都读进priority_queue,然后一个个pop，应该没什么问题呀。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

细雨微张 发表于 2019-9-14 04:13
需要再做一次检查。当把左上角元素交换到某一行之后，做一次二分搜索，检查左上角元素在这一行的位置，把 ...

有道理，不过这样子复杂度又上去了。

onewaymyway 发表于 2019-9-13 10:23
就用mergesort,先找到每行做小的那一个，和左上角的元素交换
这个不对 交换之后被选的那行就不一定是排 ...

嗯，看来不太好做。

如果可以sort in place, 直接用quick select就行了， 平均复杂度O(MN), 我觉得面试官可能想要这个答案（米不够看不到题，是找第K大吗，还是要排序整个矩阵）

merge sort split on end of row, 这样应该是利用所有信息没有更好的了吧？

in-place的话不能用quick sort吗? O(mnlogmn) 时间, 不算stack空间的话就O(1)