c********g
发帖数: 42 | 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**o
发帖数: 356 | |
d****n
发帖数: 397 | 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******n
发帖数: 12088 | 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*****g
发帖数: 71 | 5 用两个Heap，Heap要满时做table doubling，平均起来插入时间还是logN，返回min或
max时间是O(1),
或者用两个BST，插入、返回最大、最小值都是logN，可以满足速度要求，如果要加快
单纯查询时间，可以缓存min和max，插入和删除时更新一下就行了，这样查询速度是O(
1) |
c********g
发帖数: 42 | 6 Thanks!
请教一下 pmax里的元素都是sorted的么
pmax add一个元素复杂度是多少啊？底层实现是用二分搜索么？ |
b**********5
发帖数: 7881 | 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*****n
发帖数: 2152 | 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(
|
t******5
发帖数: 30 | 9 能解释一下思路么？
【在 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
|
a****r
发帖数: 87 | 10 嗯。有点不明白。如果用bst,那memory overhead不是会更大？因为BST还要保存left
and right children. Heap 一般直接用array就实现了。overhead会更小。
O(
【在 m*****g 的大作中提到】
: 用两个Heap，Heap要满时做table doubling，平均起来插入时间还是logN，返回min或
: max时间是O(1),
: 或者用两个BST，插入、返回最大、最小值都是logN，可以满足速度要求，如果要加快
: 单纯查询时间，可以缓存min和max，插入和删除时更新一下就行了，这样查询速度是O(
: 1)
|
n**s
发帖数: 2230 | 11 这题都没做过？ 经典题了。要是凭空想，不容易想出来。 |
