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

向右看齐 2023-02-18 01:47 16阅读 0赞

被面试官拒绝的写法：

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

快排：

class Solution {
        
    public:
        int partition(vector<int> &input, int l, int r){
        
            int pivot = input[l]; 
            int i = l+1; int j = r-1;
            while(i <= j) {
        
                while(input[i] < pivot) i++;
                while(input[j] > pivot) j--;
                if(i < j) swap(input[i++], input[j--]);
            }// 先根据基准将其他元素分成两块
            swap(input[l], input[j]); //再交互基准元素和比他小的分割线元素
            return j;
        }
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        
            int size = input.size();
            vector<int> v;
            if (size < k || k <= 0) return v;
            int l = 0; int r = size;
            while (l < r) {
        
                int p = partition(input, l, r);
                if(p+1 == k) return vector<int>(input.begin(), input.begin()+k);
                if(p+1 < k) l = p+1;
                else r = p;
            }
            return v;
        }
    };

堆排序，利用stl优先队列priority\_queue：

class Solution {
        
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        
            int size = input.size();
            vector<int> re;
            if(k > size || k <= 0) return re;
            priority_queue<int> q;
            for(int i = 0; i < size; i++ ){
        
                if(q.size() < k) q.push(input[i]);
                else {
        
                    if(input[i] < q.top()) {
        
                        q.pop();
                        q.push(input[i]);
                    }
                }
            }
            while(!q.empty()) {
        
                re.push_back(q.top());
                q.pop();
            }
            return re;
        }
    };