题解 | #最小的K个数#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    //完整快排思想
    int part(vector<int> &input,int low,int high){
        int pivot=input[low];//以最左侧的值作为基准
        int i=low;
        int j=high;
        while(i<j){
            //从右到左，找小的。找到了就交换位置
            while(i<j && input[j]>pivot){
                j--;
            }
            //交换位置后，比基准小的值在数组i左侧
            if(i<j)
                swap(input[i++],input[j]);
            //从左往右，找大的，找到了就交换位置
            while(i<j && input[i]<=pivot){
                i++;
            }
            //交换位置后，比基准大的值在数组i右侧
            if(i<j)
                swap(input[i],input[j--]);
        }
        //i两侧存在大小关系（左大右小）的位置作为下一次划分的依据
        return i;
    }

    void quickSort(vector<int> &input,int low,int high){
        int mid=0;
        if (low<high){
            mid=part(input,low,high);
            quickSort(input, low, mid-1); //每一次递归，排序区间缩小一半
            quickSort(input, mid+1, high);
        }
    }

    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        int low=0;
        int high=input.size()-1;
        quickSort(input, low, high);
        vector<int> rel(input.begin(),input.begin()+k);
        return rel;

        // write code here
    }
};