我想知道我的思路是否正确。
我正在准备面试（作为一名大学生），我遇到的问题之一是找到数组中最大的 K 个数字。
我的第一个想法是只使用部分选择排序（例如，从第一个元素扫描数组，并为看到的最低元素及其索引保留两个变量，并与数组末尾的该索引交换，并继续这样做，直到我们'交换了 K 个元素并返回该数组中前 K 个元素的副本）。
然而，这需要O(K*n)时间。如果我简单地使用像 Mergesort 这样的高效排序方法对数组进行排序，那么只需要O(n*log(n))是时候对整个数组进行排序并返回 K 个最大的数字了。
在面试期间讨论这两种方法是否足够好（比较输入的 log(n) 和 K 并使用两者中较小的一个来计算 K 最大），或者可以安全地假设我应该给出这个问题的 O(n) 解决方案？
存在一个O(n)寻找第 k 个最小元素的算法 http://en.wikipedia.org/wiki/Median_of_medians，一旦获得该元素，您就可以简单地扫描列表并收集适当的元素。它基于快速排序，但其工作原理背后的原因相当复杂......还有一个更简单的变体：probably将运行在O(n). 我对另一个问题的回答 https://stackoverflow.com/questions/6072319/finding-n-th-smallest-element-in-an-array/6072432#6072432包含对此的简短讨论。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
