【面试题030】最小的k个数

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

【面试题030】最小的k个数

题目：

输入n个整数，找出其中最小的k个数。

例如输入4、5、1、6、2、7、3、8这8个字，则其中最小的4个数字是1、2、3、4。

思路一：

可以同样的基于随机快速排序的Partition函数，来对数组做划分，

基于k来作调整，返回调用Partition函数，直到左边的k个数字是整个数组中最小的k个数字。

ps.这种方法要修改数组中数字的顺序，因为Partition函数会调整数组中数字的顺序。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <iostream>

using namespace std;

void Swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int Partition(int *numbers, int beg, int end)
{
//如果轴是随机取的话，这里得做一个Swap把这个轴元素交换到end位置
    int small = beg - 1;
    int index;
    for (index = beg; index < end; ++index)
    {
        if (numbers[index] <= numbers[end])
        {
            small++;
            Swap(&numbers[small], &numbers[index]);
        }
    }
    ++ small;
    Swap(&numbers[small], &numbers[end]);
    return small;
}

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

}

int main()
{
    int input[] = {4, 5, 1, 6, 2, 7, 3, 8};
    int output[4];
    int num = sizeof(input) / sizeof(input[0]);
    int k = sizeof(output) / sizeof(output[0]);
    GetLeastNumbers(input, num, output, k);
    for (int i = 0; i < k; ++i)
    {
        cout << output[i] << " ";
    }
    cout << endl;
    return 0;
}

思路二：

首先创建一个大小为k的容器来存储最小的k个数字，

遍历这n个数字，如果容器大小小于k，就放入。如果容器已经满了，则跟容器中的最大数字做比较，

如果大于最大数字，遍历下一个，如果小于当前已有的最大值，替换当前这个最大值。

如果用二叉树来实现这个容器，那么我们能在O(logk)

——我想到了最大堆，在O(1)时间内获得已有的k个数字中的最大值，但是需要O(logk)时间完成删除及插入操作。

我们可以利用红黑树来实现我们的容器，STL中set和multiset都是基于红黑树实现的。

C++ Code

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <iostream>
#include <set>
#include <vector>
using namespace std;

typedef multiset<int, greater<int> > intSet;
typedef multiset<int, greater<int> >::iterator setIterator;

void GetLeastNumbers(const vector<int> &data, intSet &leastNumbers, int k)
{
    leastNumbers.clear();
    if ( k < 1 || (int)data.size() < k )
    {
        return;
    }

vector<int>::const_iterator iter = data.begin();
    for (; iter != data.end(); ++iter)
    {
        //有符号数/无符号数不匹配
        if ((int)(leastNumbers.size()) < k)
        {
            leastNumbers.insert(*iter);
        }
        else
        {
            setIterator iterGreatest = leastNumbers.begin();

if (*iter < * (leastNumbers.begin()))
            {
                leastNumbers.erase(iterGreatest);
                leastNumbers.insert(*iter);
            }
        }
    }
}

int main()
{
    int input[] = {4, 5, 1, 6, 2, 7, 3, 8};
    intSet leastNumbers;
    vector<int> data(&input[0], &input[7]);
    GetLeastNumbers(data, leastNumbers, 4);

while(!leastNumbers.empty())
    {
        setIterator iterGreatest = leastNumbers.begin();
        cout << *iterGreatest << " ";
        leastNumbers.erase(iterGreatest);
    }

cout << endl;
return 0;
}