设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：

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

题解

方法一：排序

思路和算法

对原数组从小到大排序后取出前 kkk 个数即可。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] vec = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < k; ++i) {
            vec[i] = arr[i];
        }
        return vec;
    }
}

复杂度分析

• 时间复杂度：O(nlog⁡n)，其中 n 是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。
• 空间复杂度：O(log⁡n)，排序所需额外的空间复杂度为 O(log⁡n)。