（二十二）剑指offer之最小的k个数

题目描述：

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

时间复杂度O（n）

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result;
        int length = input.size();
        if(input.empty() || k<1 || k>length) return result;//注意输入检测
        int start = 0;
        int end = length - 1;
        int index = partition(input, start, end);
        while(index != k -1){
            if(index > k - 1){
                end = index - 1;
                index = partition(input, start, end);
            }else{
                start = index + 1;
                index = partition(input, start, end);
            }
        }
        for(int i = 0; i < k; ++i){
            result.push_back(input[i]);
        }
        return result;
    }
    int partition(vector<int> &input, int first, int last){
        int i = first;
        int j = last;
        int key = input[first];
        if(first < last){
            while(i<j){
                while(i<j && key <= input[j]) j--;
                if(i < j) input[i++] = input[j];
                while(i<j && key >= input[i]) i++;
                if(i<j) input[j--] = input[i];
            }
            input[i] = key;
        }
        return i;
    }
};

时间复杂度O（nlogk）

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

如有建议或其他问题，可随时给我们留言。或者到以下链接：

https://github.com/gaobaoru/code_day

Star/Fork/Push 您的代码，开源仓库需要您的贡献。

请查看Coding 题目网址和收藏Accepted代码仓库，进行coding！！！