部分选择排序与合并排序以查找“数组中最大的 k" [英] Partial selection sort vs Mergesort to find "k largest in array"

问题描述

我想知道我的想法是否正确.

I was wondering if my line of thinking is correct.

我正在准备面试(作为一名大学生)，我遇到的一个问题是在数组中找到 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) 时间.如果我只是使用 Mergesort 这样的高效排序方法对数组进行排序，则只需 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.

在面试中讨论这两种方法是否足够好(比较输入的 log(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) 中运行.我对另一个问题的回答包含一个简短的讨论这个.

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.

这篇关于部分选择排序与合并排序以查找“数组中最大的 k"的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！