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

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;
}