f*********i
发帖数: 197 | 1 解法应该是构造一个size 为 k的heap，时间复杂度是O(nlgk)但是有一点我想问大家，
你们是如何判断当前heap最顶端的数是属于哪个数组的呢。用hash的话会有两个key相
同的问题，一个个和数组的数比较的话那就太花时间了。
请问有没有比较好的方法判断。 |
w***y
发帖数: 6251 | 2 我当时想的是， 在heap里面放的node，除了排序用的key, 还存放数组指针 |
a****o
发帖数: 45 | |
c*******a
发帖数: 35 | 4 呵呵，那就建一个和那个heap 一摸一样的另一个堆记住每个node是来自第几个array不
就得了。
O是不变的 |
z****h
发帖数: 164 | 5 真的吗？
第一个堆存的是value，按照value大小排序。
第二个堆存的是array index，请问按照什么排序能跟第一个堆对应？
【在 c*******a 的大作中提到】
: 呵呵，那就建一个和那个heap 一摸一样的另一个堆记住每个node是来自第几个array不
: 就得了。
: O是不变的
|
f*******n
发帖数: 12623 | 6 Instead of using the number as the heap element, use a pair (number, array
number) as the element. When you compare, compare the number only (use a
custom comparator that only compares the first part of the pair). |
s*****n
发帖数: 162 | 7 n个sorted arrays，每个有n元素，求第k大的数，江湖传闻有paper给出了O(n）的解，
不过解法应该很复杂，因为这题反复讨论过，至今也没有见到O(n)的详解。退求其次，
有O(n log n)的解法，用到median of medians和weighted median。这个解法比用堆的
O(k log n)算法，有更好的时间复杂度，因为in the worst case, k是O(n^2)。但这个
解法在面试中，要写出code来，估计也不太可能。 |
c*******a
发帖数: 35 | 8 其实第二个不是一个堆，不需要根据index排序，只是一个和第一个树一样的二叉树，
只不过顺序是一样的，当你traverse第一个树的时候，同样调整第二个树即可。
【在 z****h 的大作中提到】
: 真的吗？
: 第一个堆存的是value，按照value大小排序。
: 第二个堆存的是array index，请问按照什么排序能跟第一个堆对应？
|
