题目描述

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

思路

看到题目第一反应是用冒泡排序，但是不需要全部排完序，因为只要最小的k个数，所以外循环只需要k次就行了
但是！！！注意，注意特殊情况，k大于数组长度的情况！！！

我想说

几种排序方法每次面试笔试前都得看一下思路，最好能写一下程序

代码

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> output;
        if(input.size()<=0)
            return output;
        if(k>input.size())
            return output;
        for(int i=0;i<k;i++)
        {
            int temp;
            for(int j=0;j<input.size()-i-1;j++)
            {
                if(input[j]<input[j+1])
                {
                    temp=input[j];
                    input[j]=input[j+1];
                    input[j+1]=temp;
                }
            }
            output.push_back(input[input.size()-i-1]);
        }
        return output;
    }
};