剑指 Offer 40. 最小的k个数

题目链接：剑指 Offer 40. 最小的k个数

方法：排序

解题思路

1. 基于比较的排序，最低时间复杂度为\(O(nlogn)\)，空间复杂度为\(O(1)\)；
2. 哈希计数，时间复杂度为\(O(n)\)，但需要额外的空间。

代码

// 基于比较的排序
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> ans(k);
        sort(arr.begin(), arr.end());
        for (int i = 0; i < k; i ++ ) {
            ans[i] = arr[i];
        }
        return ans;
    }
};

// hash计数
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        int cnt[10001] = {0};
        vector<int> ans(k);
        for (int i = 0; i < arr.size(); i ++ ) {
            cnt[arr[i]] ++ ;
        }
        for (int i = 0, j = 0; i < 10001 && j < k; i ++ ) {
            while (cnt[i] > 0 && j < k) {
                ans[j ++] = i;
                cnt[i] -- ;
            }
        }
        return ans;
    }
};