p*****3
发帖数: 488 | 1 Design一个数据结构，找出无限输入流中任意时刻第k大的数，
O(n)时间，O(k)空间，n为当前读入的数据个数 |
w*********m
发帖数: 4740 | 2 对于时间k算常数吗？
【在 p*****3 的大作中提到】
: Design一个数据结构，找出无限输入流中任意时刻第k大的数，
: O(n)时间，O(k)空间，n为当前读入的数据个数
|
w****x
发帖数: 2483 | |
k*********6
发帖数: 738 | 4 max heap with size K together with a min heap? |
w****x
发帖数: 2483 | 5
THink again
【在 k*********6 的大作中提到】
: max heap with size K together with a min heap?
|
p****U
发帖数: 109 | 6 size k 的minheap可以吗？ 一直读取输入，放入heap中。 |
g*********e
发帖数: 14401 | 7 一个heap不就可以了吗？
另外为啥是minheap? 我一直分不清max heap min heap哪个存最大数 |
c********e
发帖数: 186 | 8 Min-Heap，先读够k个数，然后每次读入一个数X，比较X与heap的root，如果root < X,
remove root and insert X. |
i****y
发帖数: 84 | 9 lz来解答吧，应该不是min max heap这么基础的吧？ |
w****x
发帖数: 2483 | 10
其实我也不是很清楚，
是不是可以一开始当读入数据个数小于k时候是保持k个sorted number, 然后每读入一
个，
把array当作deque, k个以后每读入一个x， 如果x小于当前deque最大的（last），
removeLast, 然后一个个removeFirst直到first >= x，然后addFirst, 保持deque递增
？
【在 i****y 的大作中提到】
: lz来解答吧，应该不是min max heap这么基础的吧？
|
d******3
发帖数: 70 | 11 你的时间是nk。更好一点是把array换成balanced BST of size k。每次读一个x,
insert, 然后Remove 最小的一个。时间nlogk。
【在 w****x 的大作中提到】
:
: 其实我也不是很清楚，
: 是不是可以一开始当读入数据个数小于k时候是保持k个sorted number, 然后每读入一
: 个，
: 把array当作deque, k个以后每读入一个x， 如果x小于当前deque最大的（last），
: removeLast, 然后一个个removeFirst直到first >= x，然后addFirst, 保持deque递增
: ？
|
g******y
发帖数: 143 | 12 With a minHeap we can get the kth maximum number at current time.
But we need get the kth maximum number at previous time. Obviously, just one
data structure is not enough.
【在 p*****3 的大作中提到】
: Design一个数据结构，找出无限输入流中任意时刻第k大的数，
: O(n)时间，O(k)空间，n为当前读入的数据个数
|
b***e
发帖数: 1419 | 13 Strictly speaking, this should not be possible. Otherwise I could use this
algorithm to develop a linear sorting algorithm:
Given an array of size k, I stream in first the array (of size k), and then
k consecutive infinity (or a really large number).
【在 p*****3 的大作中提到】
: Design一个数据结构，找出无限输入流中任意时刻第k大的数，
: O(n)时间，O(k)空间，n为当前读入的数据个数
|
