部分选择排序VS归并找到＆QUOT; k个最大的阵列QUOT; [英] Partial selection sort vs Mergesort to find "k largest in array"
问题描述
我在想，如果我的思路是正确的。
I was wondering if my line of thinking is correct.
我是preparing面试（作为大学生）和我来的一个问题是各地要找到K的人数最多在数组中。
I'm preparing for interviews (as a college student) and one of the questions I came across was to find the K largest numbers in an array.
我的第一个想法是只使用部分选择排序（例如，从第一个元素扫描阵列和保持两个变量与该指数在数组的结尾看到最低的元素，其索引和交换，并继续这样做直到我们交换k个元素，并返回第k个元素的副本，该数组）。
然而，这需要 O（K * N）的时间。如果我只是使用像归并一种有效的排序方法排序的数组，将只需要 O（N *的log（n））的时间对整个数组进行排序，并返回在K人数最多的。
My first thought was to just use a partial selection sort (e.g. scan the array from the first element and keep two variables for the lowest element seen and its index and swap with that index at the end of the array and continue doing so until we've swapped K elements and return a copy of the first K elements in that array).
However, this takes O(K*n) time. If I simply sorted the array using an efficient sorting method like Mergesort, it would only take O(n*log(n)) time to sort the entire array and return the K largest numbers.
是不是不够好，在接受记者采访时，讨论这两种方法（比较日志中输入的（n）和K和将与两个较小的计算k个最大），或者会是安全的假设，我米有望给这个问题一个O（n）的解决方案？
Is it good enough to discuss these two methods during an interview (comparing log(n) and K of the input and going with the smaller of the two to compute the K largest) or would it be safe to assume that I'm expected to give a O(n) solution for this problem?
推荐答案
存在一个 O（N）算法寻找第k最小元素，一旦你有一个元素，你可以简单地通过清单扫描和收集相应的元素。它是基于快速排序，但其背后为什么它的理由是相当多毛的......还有一个更简单的变体，的也许的将运行为O（n）。 <一href="http://stackoverflow.com/questions/6072319/finding-n-th-smallest-element-in-an-array/6072432#6072432">My回答另一个问题包含这一个简短的讨论。
There exists an O(n) algorithm for finding the k'th smallest element, and once you have that element, you can simply scan through the list and collect the appropriate elements. It's based on Quicksort, but the reasoning behind why it works are rather hairy... There's also a simpler variation that probably will run in O(n). My answer to another question contains a brief discussion of this.
这篇关于部分选择排序VS归并找到＆QUOT; k个最大的阵列QUOT;的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
