寻找最大的K个数

Posted on | In | |
Words count in article: 665 | Reading time ≈ 2

有很多个无序的数，姑且假定它们个不相等，怎么选出其中最大的若干个数呢？

解法一：

我们先假设元素的数量不大，例如在几千个左右，在这种情况下，我们就排序吧。快速排序和堆排序都是不错的选择，他们的平均时间复杂度都是O(N*log_2N)，然后取出前K个，O(K)。总时间复杂度就是前两者相加得O(N*log_2N)

题目只要求最大的K个数，并不需要前K个数有序，也不需要后N-K个数有序。

如何避免做后N-K个数的排序呢？ 我们需要部分排序算法，选择排序和交换排序（冒泡排序）都是不错的选择，把N个数中的前K个数排序出来，复杂度是O(N*K)

哪一个更好呢？O(N*log_2N)还是O(N*K)？这取决于K的大小。在K（K<=log2N）较小的情况下，可以选择部分排序。

解法二：

在快速排序中，每一步都是将待排数据分成两组，其中一组数据的任何一个数都比另一组中的任何数大，再对两组分别做类似的操作。。。

假设N个数存储在数组S中，我们从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中的元素小于X

这时有两种情况：

  1. Sa中元素的个数小于K，Sa中的所有数和Sb中最带的K-|Sa|个元素就是数组S中最大的K个数

  2. Sa中元素的个数大于或等于K，则返回Sa中最大的K个元素。

递归，平均复杂度为O(N*log2K)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//伪代码
Kbig(S, K):
    if(k <= 0):
        return []
    if(length S <= K):
        return S
    (Sa, Sb) = Partition(S)
    return Kbig(Sa, k).Append(Kbig(Sb, k - Sa.length))

Partition(S):
    Sa = []
    Sb = []
    Swap(S[1], S[Random() % S.length])

    p = S[1]
    for i in [2:S.length]:
        S[i] > p ? Sa.Append(S[i]) : Sb.Append(S[i])

    Sa.length < Sb.length ? Sa.Append(p) : Sb.Append(p)
    return (Sa, Sb)

解法三：

寻找N个数中最大的K个数，本质上就是寻找最大的K个数中最小的那个，也就是第K大的数，可以使用二分搜索的策略。

对于一个给定的数p，可以在O（N）时间复杂度内找出所有不小于p的数，假如N个数中最大的数为Vmax，最小的数为Vmin，那么这N个数中的第K大数一定在区间Vmin~Vmax之间，那么可以在这个却见内二分搜索N个数中的第K大数p

Donate? comment?