f****4
发帖数: 1359 | 1 一个NxN的矩阵数列，若此矩阵每一列都是增序的，求这NxN个数的中位数 | f*******e
发帖数: 1161 | 2 听上去像堆
【在 f****4 的大作中提到】
: 一个NxN的矩阵数列，若此矩阵每一列都是增序的，求这NxN个数的中位数
| s*****e
发帖数: 16824 | 3 这就等于找第1/2N行的中位数。
【在 f****4 的大作中提到】
: 一个NxN的矩阵数列，若此矩阵每一列都是增序的，求这NxN个数的中位数
| x*******7
发帖数: 223 | 4 感觉不是这样吧。
【在 s*****e 的大作中提到】
: 这就等于找第1/2N行的中位数。
| r****o
发帖数: 1950 | 5 大家看看我的想法对不?
可以模仿merge sort,先考虑N为偶数的情况
设这N列为c1,c2,...,cN
将c1和c2, c3和c4, ..., c_{N-1}和cN 两两 merge成一个长2N的列，设为d1,d2,...d_{N/2}
然后再将d1和d2,d3和d4,...,d{N/2-1}和d{N/2}两两merge成一个长4N的列，
如此反复merge,直到最后剩下两个长N*N/2的列，用binary search可找到median。
时间复杂度，O(N)+O(2N)+...+O(N*N/2)+O(2lgN)=O(N^2 lgN).
空间复杂度O(N^2).
当N为奇数时，可将最中间那列先空着，当左右两边都merge成了长(N-1)N/2的列后，再merge成一个长(N-1)N的大列，然后问题可归结为一个长(N-1)N的列和一个长N的列，都排好序，找median的问题。
时间复杂度和空间复杂度应该和偶数时一样。
【在 f****4 的大作中提到】
: 一个NxN的矩阵数列，若此矩阵每一列都是增序的，求这NxN个数的中位数
| d****e
发帖数: 251 | 6 没必要merge阿， 每列都是增序了。
这里的好处是NxN，直接比较N个median, 可能可以转换为比较两列的问题。
可能比facebook那道题还简单。
d_{N/2}
再merge成一个长(N-1)N的大列，然后问题可归结为一个长(N-1)N的列和一个长N的列，
都排好序，找median的问题。
【在 r****o 的大作中提到】
: 大家看看我的想法对不?
: 可以模仿merge sort,先考虑N为偶数的情况
: 设这N列为c1,c2,...,cN
: 将c1和c2, c3和c4, ..., c_{N-1}和cN 两两 merge成一个长2N的列，设为d1,d2,...d_{N/2}
: 然后再将d1和d2,d3和d4,...,d{N/2-1}和d{N/2}两两merge成一个长4N的列，
: 如此反复merge,直到最后剩下两个长N*N/2的列，用binary search可找到median。
: 时间复杂度，O(N)+O(2N)+...+O(N*N/2)+O(2lgN)=O(N^2 lgN).
: 空间复杂度O(N^2).
: 当N为奇数时，可将最中间那列先空着，当左右两边都merge成了长(N-1)N/2的列后，再merge成一个长(N-1)N的大列，然后问题可归结为一个长(N-1)N的列和一个长N的列，都排好序，找median的问题。
: 时间复杂度和空间复杂度应该和偶数时一样。
| H****r
发帖数: 2801 | 7 D&C?
【在 f****4 的大作中提到】
: 一个NxN的矩阵数列，若此矩阵每一列都是增序的，求这NxN个数的中位数
| h**6
发帖数: 4160 | 8 把N个中位数拿来比较，然后有N/2个大的和N/2个小的，把那N/2列比小中位数还小的和
那N/2列比大中位数还大的去掉，然后接着比。考虑奇偶数和可能相等的问题，还是比
较复杂的。 | m****w
发帖数: 372 | 9 多路merge sort , 同时用堆维护当前最小值，直到merge到第 N^2/2 个数为止
time: O(N^2/2 * logN)
space: O( N ) | s*******s
发帖数: 27 | 10 这个解法是对的。不知道in-place有没有什么好的解法？
【在 m****w 的大作中提到】
: 多路merge sort , 同时用堆维护当前最小值，直到merge到第 N^2/2 个数为止
: time: O(N^2/2 * logN)
: space: O( N )
| r****o
发帖数: 1950 | 11 问一下，为什么要用一个堆维护当前最小值? 是Min堆还是Max堆，具体是怎么操作的呢
？多谢。
【在 m****w 的大作中提到】
: 多路merge sort , 同时用堆维护当前最小值，直到merge到第 N^2/2 个数为止
: time: O(N^2/2 * logN)
: space: O( N )
| f*p
发帖数: 100 | 12 顶这个。
【在 s*****e 的大作中提到】
: 这就等于找第1/2N行的中位数。
| l******c
发帖数: 2555 | 13 not right apparently. Only true if both row and col are sorted(now, only row
sorted)
【在 f*p 的大作中提到】
: 顶这个。
|
|
