题解 | #最小的K个数#

第一次我用快排思想做的，不过是快排变形，测试完效率奇低；我太傻了，一看可以用大根堆做的

class Solution {
public:
    int quick(vector<int> &vec,int low,int high){
        if(low>=high)
            return low;
        int middle = (low+high)/2;
        middle = (vec[middle]>vec[low]?vec[middle]:vec[low])<vec[high]?(vec[middle]>vec[low]?middle:low):high;
        int flag = vec[middle];
        vec[middle] = vec[low];
        while(low<high){
            while(low<high&&vec[high]>=flag) high--;
            vec[low] = vec[high];
            while(low<high&&vec[low]<=flag) low++;
            vec[high] = vec[low];
        }
        vec[low] = flag;
        return low;
    }
    int quicksort(vector<int> &vec,int low,int high,int k,vector<int> &state){
        int loc;
        int size = state.size();
        int sta;
        int l = 0;
        do{
            sta = 1;
            for(int i=0;i<k;i++){
                sta *= state[i];
                if(!sta){
                    l = i;
                    break;
                }
            }
            for(int i=0;!sta&&i+1<size;i++){
                if(i+2==size&&vec[i]<=vec[i+1]){
                    sta = 1;
                }
                if(vec[i]>vec[i+1]) break;
            }
            if(!sta){
                int head,tail;
                head = tail =l;
                while(head>low&&!state[head-1]) head--;
                while(tail<high&&!state[tail+1]) tail++;
                loc = quick(vec, head, tail);
                state[loc] = 1;
            }
        }while(!sta);
        return loc;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> state(input.size(),0);
        quicksort(input, 0, input.size()-1,k,state);
        vector<int> ans(input.begin(),input.begin()+k);
        return ans;
    }
};

这下面是正儿八经的快排思想，但效率还是不高下次试试堆排

class Solution {
public:
    int quick(vector<int> &vec,int low,int high){
        if(low>=high)
            return low;
        int middle = (low+high)/2;
        middle = (vec[middle]>vec[low]?vec[middle]:vec[low])<vec[high]?(vec[middle]>vec[low]?middle:low):high;
        int flag = vec[middle];
        vec[middle] = vec[low];
        while(low<high){
            while(low<high&&vec[high]>=flag) high--;
            vec[low] = vec[high];
            while(low<high&&vec[low]<=flag) low++;
            vec[high] = vec[low];
        }
        vec[low] = flag;
        return low;
    }
    int quicksort(vector<int> &vec,int low,int high,int k,vector<int> &state){
        if(low>=high) return 1;
        int loc = quick(vec,low,high);
        state[loc] = 1;
        int size = state.size();
        for(int i=0;i+1<size;i++){
            if(i+2==size&&vec[i]<=vec[i+1]){
                    return 1;
             }
            if(vec[i]>vec[i+1]) break;
        }
        int pre=1,later=1;
        for(int i = 0;i<loc;i++){
            pre *=state[i];
        }
        for(int i = 1;i+loc<k;i++){
            later *=state[i+loc];
        }
        int head,tail;
        if(!pre){
            quicksort(vec,low, loc-1, k,state);
        }
        if(!later){
            quicksort(vec,loc+1, high, k,state);
        }

        return loc;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> state(input.size(),0);
        quicksort(input, 0, input.size()-1,k,state);
        vector<int> ans(input.begin(),input.begin()+k);
        return ans;
    }
};