y*******6
发帖数: 173 | 1 就是一个大数组里面（unsorted) 要找sum of 最大的k 个数
int kSum (int [] array, int k);
不就是用heap (priorityQueue) keep the biggest k number 吗? 还能有什么更好的
方法吗？ 面试的好像说有，但不说怎么办。 |
S********t
发帖数: 3431 | 2 kth largest element can be found in O(n)
I think you can find it in algo textbook, or just google it
【在 y*******6 的大作中提到】
: 就是一个大数组里面（unsorted) 要找sum of 最大的k 个数
: int kSum (int [] array, int k);
: 不就是用heap (priorityQueue) keep the biggest k number 吗? 还能有什么更好的
: 方法吗？ 面试的好像说有，但不说怎么办。
|
V***a
发帖数: 206 | 3 类似quick sort的算法，复杂度O(n)，好像叫quick select来着，能找到最大的k个数。 |
y**********a
发帖数: 824 | 4
median of medians.
The nth element of the array after you run the algorithm will be the nth
biggest element, and the right side will be of all bigger numbers bigger
than the nth.
The complexity of the algorithm is O(n).
【在 y*******6 的大作中提到】
: 就是一个大数组里面（unsorted) 要找sum of 最大的k 个数
: int kSum (int [] array, int k);
: 不就是用heap (priorityQueue) keep the biggest k number 吗? 还能有什么更好的
: 方法吗？ 面试的好像说有，但不说怎么办。
|
w****e
发帖数: 586 | 5 已知完整数组的，直接一遍quickselect，然后再遍历一遍。平均O(n)
如果数据是stream进来的，不知道有多长，就维护一个2k长的vector，数据每填满2k个
就quickselect一遍，筛掉k个。最后平均也还是O(n) |
x**1
发帖数: 892 | 6
不是很懂 stream进来的办法
你删掉了1k个 万一这1k个里面有的数是最后答案里面的呢 这个时候你又不知道最终
kth是多少
【在 w****e 的大作中提到】
: 已知完整数组的，直接一遍quickselect，然后再遍历一遍。平均O(n)
: 如果数据是stream进来的，不知道有多长，就维护一个2k长的vector，数据每填满2k个
: 就quickselect一遍，筛掉k个。最后平均也还是O(n)
|
w****e
发帖数: 586 | 7 我说的情况是事先知道k，但不知道总输入有多长。
这里的k是kth的k，不是一千。。
【在 x**1 的大作中提到】
:
: 不是很懂 stream进来的办法
: 你删掉了1k个 万一这1k个里面有的数是最后答案里面的呢 这个时候你又不知道最终
: kth是多少
|
