【剑指offer】最小的K个数

题目描述

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

思路

有很多排序的算法，最简单可以用sort直接取出前K个数，然后下面就展示一种算法：归并（O(nlogn)），感觉比较稳定，然后时间复杂度也还可以，如果对其它排序有兴趣的童鞋可以进讨论区自行学习：https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?f=discussion

代码

class Solution {
public:
    void sub_merge(vector<int> &a,int s,int m,int e){
        vector<int> t;//将有序的左右两边归并到新数组中，然后再拷贝
        int p1 = s;
        int p2 = m+1;
        while(p1 <= m && p2 <= e){
            if(a[p1] <= a[p2]){
                t.push_back(a[p1]);
                p1++;
            }
            else{
                t.push_back(a[p2]);
                p2++;
            }
        }
        while(p1 <= m){
            t.push_back(a[p1]);
            p1++;
        }
        while(p2 <= e){
            t.push_back(a[p2]);
            p2++;
        }
        for(int i = 0; i <= e-s; i++){
            a[s+i] = t[i];
        }
    }
    void merge(vector<int> &a,int s,int e){
        if(e > s){
            int m = (s+e)/2;
            merge(a,s,m);//将左边从小到大排序
            merge(a,m+1,e);//将右边从小到大进行排序
            sub_merge(a,s,m,e);//将左右两边进行归并
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> vec;
        if(!input.size() || k > input.size()){
            return vec;
        }
        merge(input,0,input.size()-1);
        for(int i = 0; i < k; i++){
            vec.push_back(input[i]);
        }
        return vec;
    }
};