请教一道题 median ii - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道题 median ii

请教一道题 median ii# JobHunting - 待字闺中

c*g2015-02-21 08:02

1 楼

原题：http://lintcode.com/en/problem/median-ii/
Numbers keep coming, return the median of numbers at every time a new number
added.
Time requirement: O(nlogn)
谢谢！

l*o2015-02-21 08:02

2 楼

用一个最大堆，一个最小堆？

d*n2015-02-21 08:02

3 楼

用两个heap.一个max heap，一个min heap， maxheap size ＝ min heap size 或者
maxheap size ＝ minheapsize ＋ 1.
java implementation
public class Solution {
/**
* @param nums: A list of integers.
* @return: the median of numbers
*/
public int[] medianII(int[] nums) {
// write your code here
PriorityQueue pmin = new PriorityQueue ();
PriorityQueue pmax = new PriorityQueue (10, new
MaxComparator());
int i, l = nums.length;
int[] median = new int[l];
for(i = 0; i < l; i ++) {
if (pmin.size() == 0 && pmax.size() == 0) {
pmax.add(new Integer(nums[i]));
}
else {
if (nums[i] > pmax.peek().intValue()) pmin.add(new Integer(
nums[i]));
else pmax.add(new Integer(nums[i]));
if (pmax.size() < pmin.size()) {
Integer temp = pmin.poll();
pmax.add(temp);
}
else if (pmax.size() > pmin.size() + 1) {
Integer temp = pmax.poll();
pmin.add(temp);
}
else ;
}
median[i] = pmax.peek();
}
return median;
}

};
class MaxComparator implements Comparator {
@Override
public int compare(T t1, T t2) {
Integer i1 = (Integer) t1;
Integer i2 = (Integer) t2;
return -i1.compareTo(i2);
}
}

number

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

: 原题：http://lintcode.com/en/problem/median-ii/
: Numbers keep coming, return the median of numbers at every time a new number
: added.
: Time requirement: O(nlogn)
: 谢谢！

n*n2015-02-21 08:02

4 楼

堆大小是多少？所有元素都存着？溢出怎么办？

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

: 用两个heap.一个max heap，一个min heap， maxheap size ＝ min heap size 或者
: maxheap size ＝ minheapsize ＋ 1.
: java implementation
: public class Solution {
: /**
: * @param nums: A list of integers.
: * @return: the median of numbers
: */
: public int[] medianII(int[] nums) {
: // write your code here

m*g2015-02-21 08:02

5 楼

用两个Heap，Heap要满时做table doubling，平均起来插入时间还是logN，返回min或
max时间是O(1),
或者用两个BST，插入、返回最大、最小值都是logN，可以满足速度要求，如果要加快
单纯查询时间，可以缓存min和max，插入和删除时更新一下就行了，这样查询速度是O(
1)

c*g2015-02-21 08:02

6 楼

Thanks!
请教一下 pmax里的元素都是sorted的么
pmax add一个元素复杂度是多少啊？底层实现是用二分搜索么？

b*52015-02-21 08:02

7 楼

i think he meant what if there's no memory left to grow the heap...

O(

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

: 用两个Heap，Heap要满时做table doubling，平均起来插入时间还是logN，返回min或
: max时间是O(1),
: 或者用两个BST，插入、返回最大、最小值都是logN，可以满足速度要求，如果要加快
: 单纯查询时间，可以缓存min和max，插入和删除时更新一下就行了，这样查询速度是O(
: 1)

m*n2015-02-21 08:02

8 楼

几个想法：
每个元素，要加ref count，对付重复元素多的情况。
没必要每次动态平衡，可以计算shift，来对付查询。如果O(logN)的查询也是可以接受
的吧。
如果memory装不下，写入disk，去掉写入的data，以后有必要的时候再读出来。

【在 b**********5 的大作中提到】

: i think he meant what if there's no memory left to grow the heap...
:
: O(