h**k
发帖数: 3368 | 1 求the first k largest elements in a unsorted array.
如果k很小，比如3，n很大，比如100000，用什么算法最好？
如果k很大，接近n，用什么算法好？
进一步问如何求前 k1至 k2个最大元素（k1
如果有duplicate value在数组中，你的算法还可以么？
将来如果有机会面试别人，我一定出这道题。可惜要先找到工作，:-( |
m****o
发帖数: 34 | 2 真有闲心
【在 h**k 的大作中提到】
: 求the first k largest elements in a unsorted array.
: 如果k很小，比如3，n很大，比如100000，用什么算法最好？
: 如果k很大，接近n，用什么算法好？
: 进一步问如何求前 k1至 k2个最大元素（k1: 如果有duplicate value在数组中，你的算法还可以么？
: 将来如果有机会面试别人，我一定出这道题。可惜要先找到工作，:-(
|
r****o
发帖数: 1950 | 3 试着答一下。
就顺序比较吧，每个比较k次，复杂度O(kn)
可以排序，或binary search，或用min heap，复杂度分别是O(nlgn),O(nlgn),O(klgn)
先找出第k1大的元素，再找出第k2大的元素，介于这两者之间的元素就是所求的元素。
复杂度O(k2 lgn)
binary search的方法可能不行了，用排序和min heap应该还可以。
【在 h**k 的大作中提到】
: 求the first k largest elements in a unsorted array.
: 如果k很小，比如3，n很大，比如100000，用什么算法最好？
: 如果k很大，接近n，用什么算法好？
: 进一步问如何求前 k1至 k2个最大元素（k1: 如果有duplicate value在数组中，你的算法还可以么？
: 将来如果有机会面试别人，我一定出这道题。可惜要先找到工作，:-(
|
h**k
发帖数: 3368 | 4
klgn)
用min heap的复杂度是O(nlogk),heap的大小是k，一共插入n个元素。
用binary search的思路可以实现O(n+k)
可以的，需要改一下算法。
【在 r****o 的大作中提到】
: 试着答一下。
:
: 就顺序比较吧，每个比较k次，复杂度O(kn)
: 可以排序，或binary search，或用min heap，复杂度分别是O(nlgn),O(nlgn),O(klgn)
: 先找出第k1大的元素，再找出第k2大的元素，介于这两者之间的元素就是所求的元素。
: 复杂度O(k2 lgn)
: binary search的方法可能不行了，用排序和min heap应该还可以。
|
r****o
发帖数: 1950 | 5
恩，我写错了。
能不能说说用binary search怎么实现O(n+k)啊? 我觉得有binary search，复杂度里面
应该有个lg啊。
能否说说怎么改进?
【在 h**k 的大作中提到】
:
: klgn)
: 用min heap的复杂度是O(nlogk),heap的大小是k，一共插入n个元素。
: 用binary search的思路可以实现O(n+k)
: 可以的，需要改一下算法。
|
a*d
发帖数: 47 | 6 "如果k很大，接近n，用什么算法好".
similar to the case that k is small.
Because, we can eliminate (n-k) smallest elements, and remaining ones are k
largest.
klgn)
【在 r****o 的大作中提到】
: 试着答一下。
:
: 就顺序比较吧，每个比较k次，复杂度O(kn)
: 可以排序，或binary search，或用min heap，复杂度分别是O(nlgn),O(nlgn),O(klgn)
: 先找出第k1大的元素，再找出第k2大的元素，介于这两者之间的元素就是所求的元素。
: 复杂度O(k2 lgn)
: binary search的方法可能不行了，用排序和min heap应该还可以。
|
h**k
发帖数: 3368 | 7
其实是类似quick sort的思路，每次二分数组的时候，得到前半个部分的大小，如果小
于k,则舍弃后半部分，否则输出前半部分，在后半部分找剩下的。
【在 r****o 的大作中提到】
:
: 恩，我写错了。
: 能不能说说用binary search怎么实现O(n+k)啊? 我觉得有binary search，复杂度里面
: 应该有个lg啊。
: 能否说说怎么改进?
|
h*******e
发帖数: 225 | 8 那也不是O(n+k)
【在 h**k 的大作中提到】
:
: 其实是类似quick sort的思路，每次二分数组的时候，得到前半个部分的大小，如果小
: 于k,则舍弃后半部分，否则输出前半部分，在后半部分找剩下的。
|
r****o
发帖数: 1950 | 9 这个复杂度好像是O(n lgk)
【在 h**k 的大作中提到】
:
: 其实是类似quick sort的思路，每次二分数组的时候，得到前半个部分的大小，如果小
: 于k,则舍弃后半部分，否则输出前半部分，在后半部分找剩下的。
|
h**k
发帖数: 3368 | 10 第一次需要比较整个数组，c*n次运算，c是常数，第二次只需要比较一半的数组，c*n/
2，。。。，
总的运算次数是c*n+c*n/2+c*n/4+... <= c*2*n
因为一定要输出k个值，所以最终是O(n+k)
【在 h*******e 的大作中提到】
: 那也不是O(n+k)
|
|
|
l*****a
发帖数: 14598 | 11 for unsorted array,how do you know which should be discarded
and which should be kept
【在 h**k 的大作中提到】
: 第一次需要比较整个数组，c*n次运算，c是常数，第二次只需要比较一半的数组，c*n/
: 2，。。。，
: 总的运算次数是c*n+c*n/2+c*n/4+... <= c*2*n
: 因为一定要输出k个值，所以最终是O(n+k)
|
h*******e
发帖数: 225 | 12 depends on how u choose the pivot, this is expected O(N) on average, not
worst case.
n/
【在 h**k 的大作中提到】
: 第一次需要比较整个数组，c*n次运算，c是常数，第二次只需要比较一半的数组，c*n/
: 2，。。。，
: 总的运算次数是c*n+c*n/2+c*n/4+... <= c*2*n
: 因为一定要输出k个值，所以最终是O(n+k)
|
h**k
发帖数: 3368 | 13 randomly choose the pivot.
【在 h*******e 的大作中提到】
: depends on how u choose the pivot, this is expected O(N) on average, not
: worst case.
:
: n/
|
g*****e
发帖数: 282 | 14 这个思路是divide and conquer，不是binary search。经典的求k largest element的
算法之一，不需要是sorted array。但平均time complexity是nlogn.
【在 h**k 的大作中提到】
: randomly choose the pivot.
|
y******5
发帖数: 43 | 15 CLRS Selection in expected (also has worst-case) linear time. O(n)
不过我觉得在面试中只要答出expected linear time的算法就可以了吧。 |
m****v
发帖数: 84 | 16
真正O(n)的算法很复杂
【在 y******5 的大作中提到】
: CLRS Selection in expected (also has worst-case) linear time. O(n)
: 不过我觉得在面试中只要答出expected linear time的算法就可以了吧。
|
p*******y
发帖数: 50 | 17 怎么看上去很象以前Google问我的题。。。
【在 h**k 的大作中提到】
: 求the first k largest elements in a unsorted array.
: 如果k很小，比如3，n很大，比如100000，用什么算法最好？
: 如果k很大，接近n，用什么算法好？
: 进一步问如何求前 k1至 k2个最大元素（k1: 如果有duplicate value在数组中，你的算法还可以么？
: 将来如果有机会面试别人，我一定出这道题。可惜要先找到工作，:-(
|
