不忘初心

少年,专心练剑吧

最小的k个数

发表于 更新于 分类于

题目

输入n个数，找出其中最小的k个数。例如输入 4、5、1、6、2、7、3、8 这8个数字，则最小的4个数字是 1、2、3、4 。
镜像问题：找出最大的k个数问题，思路相同。
最简单的思路是把输入的n个整数从小到大排序，排序之后位于最前面的k个数就是最小的k个数。这种思路的时间复杂度是O(nlogn)。

解法一

O(n)的算法，只有可以修改输入的数组时可用。

可以利用Partition函数来解决这个问题，如果基于数组的第k个数来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字（无序）。

代码（cpp）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void GetLeastNumbers(int* input, int n, int* output, int k)
{
    if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
        return;

    int start = 0;
    int end = n - 1;
    int index = Parttion(input, n, start, end);
    while(index != k -1)
    {
        if(index > k -1)
        {
            end = index - 1;
            index = Partition(input, n, start, end);
        }
        else
        {
            start = index + 1;
            index = Partition(input, n, start, end);
        }
    }
    for(int i = 0; i < k; ++i)
        output[i] = input[i];

}

解法二

O(nlogk)的算法，特别适合处理海量数据。

关键的数据结构：最大堆。

在C++的STL中set和multiset都是基于红黑树实现的。

代码（cpp）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef multiset<int, greater<int>> inSet;//最大堆
typedef multiset<int, greater<int>>::inerator setIterator;
void GetLeastNumbers(const vector<int>&data, inSet& leastNumbers, int k)
{
    leastNumbers.clear();
    if(k < 1 || data.size() < k)
        return;
    vector<int>::const_iterator iter = data.begin();
    for(; iter != data.end(); ++ iter)
    {
        if((leastNumbers.size()) < k)
            leastNumbers.insert(*iter);
        else
        {
            setIterator iterGreatest = leastNumbers.begin();//取出最大数
            if(*iter < *(leastNumbers.begin()))
            {
                leastNumbers.erase(iterGreatest);
                leastNumbers.insert(*iter);
            }
        }
    }
}