首页 文章

部分选择排序vs Mergesort找到“k最大的数组”

提问于
浏览 330
1

我想知道我的思路是否正确 .

我正在准备面试(作为一名大学生),我遇到的一个问题是在阵列中找到K个最大的数字 .

我的第一个想法是仅使用部分选择排序(例如,从第一个元素扫描数组并保留两个变量用于所见的最低元素及其索引,并在数组末尾与该索引交换并继续这样做直到我们'我交换了K个元素并返回该数组中前K个元素的副本) . 但是,这需要 O(K*n) 时间 . 如果我只是使用像Mergesort这样的高效排序方法对数组进行排序,那么只需要 O(n*log(n)) 时间对整个数组进行排序并返回K个最大数字 .

在访谈中讨论这两种方法是否足够好(比较输入的log(n)和K以及两者中的较小者来计算K最大值)或者可以安全地假设我期望为这个问题提供O(n)解决方案?

4 回答

  • 3

    存在O(n) algorithm for finding the k'th smallest element,一旦您拥有该元素,您只需扫描列表并收集适当的元素即可 . 它's based on Quicksort, but the reasoning behind why it works are rather hairy... There'也是一个更简单的变种,可能会在 O(n) 中运行 . My answer to another question包含对此的简要讨论 .

  • 0

    以下是通过谷歌搜索找到的这个特定访谈问题的一般性讨论:

    http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

    至于你关于一般采访的问题,可能在很大程度上取决于采访者 . 他们通常喜欢看你如何看待事物 . 因此,只要您能够提出某种初步解决方案,您的面试官就可能会根据他们正在寻找的内容提出问题 .

  • 0

    恕我直言,我认为如果他说数据集很大(比如10亿个元素),面试官会对这两种方法都不满意 . 在这种情况下,如果要返回的 K 很大(接近十亿),您的部分选择几乎会导致 O(n^2) . 我认为这完全取决于提出的问题的复杂性 .

    编辑:Aasmund Eldhuset的答案向您展示如何实现 O(n) 时间的复杂性 .

  • 0

    如果你想找到K(所以对于K = 5你会得到五个结果 - 五个最高数字)那么你能得到的最好的是 O(n+klogn ) - 你可以在 O(n) 中 Build prority队列然后调用 pq.Dequeue() k次 . 如果你正在寻找K最大的 number 那么你可以通过 O(n) 快速修改来获得它 - 它被称为 k-th order statistics . 伪代码看起来像这样:(它是随机算法,平均时间约为 O(n) 但是最坏的情况是 O(n^2)

    QuickSortSelection(numbers, currentLength, k) {
        if (currentLength == 1)
          return numbers[0];
        int pivot = random number from numbers array;
    
        int newPivotIndex = partitionAroundPivot(numbers) // check quicksort algorithm for more details - less elements go left to the pivot, bigger elements go right
    
        if ( k == newPivotIndex )
            return pivot;
        else if ( k < newPivotIndex )
            return QuickSortSelection(numbers[0..newPivotIndex-1], newPivotIndex, k)
        else
           return QuickSortSelection(numbers[newPivotIndex+1..end], currentLength-newPivotIndex+1, k-newPivotIndex);
    }
    

    正如我所说,这种算法最糟糕的情况是因为枢轴是随机选择的(但运行时间〜^ ^ 2的概率类似于 1/2^n ) . 您可以使用例如 median of three median 作为枢轴将相同运行时最坏情况转换为确定性算法 - 但它在实践中较慢(由于常量) .

相关问题