LeetCode 17.14 - Smallest K LCCI

Description

Design an algorithm to find the smallest K numbers in an array.

Example

Example 1:

Input: arr = [1,3,5,7,2,4,6,8], k = 4
Output: [1,2,3,4]

Note

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

---

思路分析

水题。给出原理相同但思路相反的两个方法：

• 使用algorithm库中的partial_sort，排出最小的k个数，并将这k个数拷贝到新的容器中，返回即可。
• 使用algorithm库中的partial_sort，排出最大的size() - k个数，并将未排序的k个数拷贝到新的容器中，返回即可。

唯一不同的是，第二种方法需使用greater()排序函数。

推荐使用方法1，速度较快。

---

代码实现

方法1

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        partial_sort(arr.begin(), arr.begin() + k, arr.end());
        vector<int> ans(arr.begin(), arr.begin() + k);
        return ans;
    }
};

方法2

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        partial_sort(arr.begin(), arr.begin() + arr.size() - k, arr.end(), greater<int>());
        vector<int> ans(arr.begin() + arr.size() - k, arr.end());
        return ans;
    }
};