题解 | #最小的K个数#

思路

参考剑指offer
1、首先使用快排的思想，对一个数组进行分割，大于某个值的在其右侧，小于某个值的在其左侧，该函数(Partition)返回一个索引，代表选择的数字的下标（可能有点绕）。
2、然后就是根据这个返回的索引和k-1（需要k个数，下标范围就是0~k-1）比较，若返回的index<k-1，那么说明第k-1小的数字在index的右侧，更新区间，计算新的index。

代码

class Solution {
public:

    void swap(int& a, int& b){
        int tmp = a;
        a = b;
        b = tmp;
    }

    // 对下标为i的构建堆
    void heapify(vector<int>& arr, int n, int i ){
        if(i>n){return;}
        int c1 = 2*i+1;
        int c2 = 2*i+2;
        int min_index = i;

        if(c1<=n && arr[c1]<arr[min_index]){
            min_index = c1;
        }
        if(c2<=n && arr[c2]<arr[min_index]){
            min_index = c2;
        }

        //min_index = 
        if(min_index==i){
            ;
        }

        else{
            swap(arr[min_index], arr[i]);
        }

        // 递归
        heapify(arr, n, c1);
        heapify(arr, n, c2);

        return;

    }

    // 构建堆
    void build_heap(vector<int>& arr, int n){
        // 找到第一个构建堆的节点
        int parent = (n-1)/2;
        while(parent>=0){
            heapify(arr, n, parent);
            parent--;
        }
    }


    // 快速排序
    int Partition(vector<int>& arr, int L, int R){
        int left = L;
        int right = R;
        int key = arr[left];
        while(left<right){
            while(left<right && arr[right] >= key){
                right--;
            }
            arr[left] = arr[right];
//             left++;

            while(left < right && arr[left]<=key){
                left++;
            }
            arr[right] = arr[left];

        }
        arr[left] = key;
        return left;

    }

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
//         // 方法1 傻子排序
//         sort(input.begin(), input.end());
//         vector<int> res;
//         res.assign(input.begin(), input.begin()+k);
//         return res;

        /*
        // 方法2 堆排序，通过构建堆
        vector<int> res;
        int count = 0;
        int len = input.size()-1;
        while(count<k){
            build_heap(input, len);        // 最小值放在堆顶
            swap(input[0], input[len]);
            res.push_back(input[len]);
            len--;
            count++;
        }
        return res;
        */

        // 方法3 利用快排
        if(k==0){
//             vector
            return vector<int>();
        }
        int start = 0;
        int end = input.size()-1;
        int index = Partition(input, start, end);

        while(index!=k-1){
            if(index<k-1){
                start = index+1;
                index = Partition(input, start, end);
            }
            else{
                end = index-1;
                index = Partition(input, start, end);
            }


        }

        vector<int> res;
        res.assign(input.begin(), input.begin()+index+1);

        return res;

    }
};