最小的K个数

题目描述

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

示例1

输入

[4,5,1,6,2,7,3,8],4

返回值

[1,2,3,4]

题解

|算法|最优时间|最差时间|平均时间|稳定性
|:---|:---|:---|:---|:---|:---
|插入排序|O(n)|O(n²)|O(n²)|稳定

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if (k <= 0 || input.empty() || k > input.size()) {
            return res;
        }
        for (int i = 0; i < input.size(); i++) {
            int index = 0;
            for (int j = res.size() - 1; j >= 0; j--) {
                if (res[j] <= input[i]) {
                    index = j + 1;
                    break;
                }
            }
            res.insert(res.begin() + index, input[i]);
            if (res.size() > k) {
                res.pop_back();
            }
        }
        return res;
    }
};