28、最小的k个数（TopK）

题目描述：

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

解题思路：

1、完全排序O(n*logn)

  没什么好说的，先排序再选择前K个数。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int sz = input.size();
        vector<int> vec;
        if (sz == 0 || k <= 0 || sz < k)
            return vec;
        sort(input.begin(), input.end());
        for (int i = 0; i < k; ++i)
            vec.push_back(input[i]);
        return vec;
    }
};

2、部分选择排序O(n*k)

  因为只需要前K个数，所以不用排序全部的数，只需要通过K次排序找到K个最小的数即可。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int sz = input.size();
        vector<int> vec;
        if (sz == 0 || k <= 0 || sz < k)
            return vec;
        for (int i = 0; i < k; ++i)
        {
            for (int j = i + 1; j < sz; ++j)
            {
                if (input[i] > input[j])
                    swap(input[i], input[j]);
            }
            vec.push_back(input[i]);
        }
        return vec;
    }
};

3、最大堆O(nlogk)

1. 首先选取前K个数建立最大堆（根结点值大于左右结点值）。

2. 此后，每次从原数组中取一个元素与根进行比较，如果大于根结点的元素，忽视之，取下一个数组元素继续该过程；如果小于根结点的元素，则将其加入最大堆，并进行堆调整，将根元素移动到最后再删除，即保证最大堆中的元素仍然是排名前K的数，且根元素仍然最大。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int sz = input.size();
        vector<int> vec;
        if (sz == 0 || k <= 0 || sz < k)
            return vec;
        for (int i = 0; i < k; ++i)
            vec.push_back(input[i]);
        // 以数组前k个元素建立初始的最大堆
        make_heap(vec.begin(), vec.end(), less<int>());
        for (int i = k; i < sz; ++i)
        {
            if (input[i] > vec.front()) // 如果接下来的元素比堆顶元素大，直接跳过
                continue;
            else // 如果接下来的元素比堆顶元素小，则调整堆
            {
                vec.push_back(input[i]);
                // 添加新元素调整堆
                push_heap(vec.begin(), vec.end());
                // 将堆顶元素调整到最后
                pop_heap(vec.begin(), vec.end());
                // 删除最后那个元素
                vec.pop_back();
            }
        }
        // 以上方法得到的只是求了TopK，但是并未排序，所以使用sort_heap排序一下
        sort_heap(vec.begin(), vec.end());
        return vec;
    }
};

【该算法有两个明显的优点】：

• 没有修改输入的数据（代码中的变量data）。我们每次只是从data中读入数字，所有的写操作都是在容器leastNumbers中进行的。

• 该算法适合海量数据的输入，不需要将数据一次性全部载入内存。

4、基于快排的算法O(n)

1. 利用快速排序划分的思想，每一次划分就会有一个数字位于以数组从小到达排列的的最终位置location（假设下标从1开始）；

2. 位于index左边的数字都小于location对应的值，右边都大于location指向的值；所以，当location> k时，表示k个最小数字一定在location的左边，此时，只需要对location的左边进行划分即可；

3. 当location< k 时，说明location及location左边数字还没能满足k个数字，需要继续对location右边进行划分。

4. 当index = k 时，说明已划分完。

class Solution {
public:
    int partition(vector<int>& arr, int low, int high)
    {
        int pivot = arr[high]; // 选最后一个元素作为枢纽元
        int location = low; // location放置的是最新的比枢纽元小的元素
        for (int i = low; i < high; i++) // 比枢纽元小的元素依次放在前半部分
            if (arr[i] < pivot)
                swap(arr[i], arr[location++]); // 移动location
        swap(arr[high], arr[location]); // 最后交换的是arr[high]，不是pivot
        return location;
    }
    void quick_sort(vector<int>& arr, int low, int high, int k)
    {
        if (low < high)
        {
            int middle = partition(arr, low, high);
            // 如果middle大于k-1，则说明arr[middle]右边的元素都大于k，于是只递归arr[low, middle-1]即可
            if (middle > k - 1)
                quick_sort(arr, low, middle-1, k);
            // 如果middle小于k-1，则说明arr[middle]左边的元素都小于k，于是只递归arr[middle+1, high]即可
            if (middle < k - 1)
                quick_sort(arr, middle+1, high, k);
            // 如果middle等于k-1说明前k个元素已经找到
            if (middle == k - 1)
                return;
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int sz = input.size();
        vector<int> vec;
        if (sz == 0 || k <= 0 || sz < k)
            return vec;
        quick_sort(input, 0, input.size() - 1, k);
        for (int i = 0; i < k; ++i)
        {
            vec.push_back(input[i]);
        }
        return vec;
    }
};