【刷穿 LeetCode】面试题 17.14. 最小K个数:「优先队列（堆）」&「全排序」&「数组划分」

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

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->a-b);
        for (int i : arr) q.add(i);
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = q.poll();
        return ans;
    }
}
复制代码

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        int[] ans = new int[k];
        if (k == 0) return ans;
        for (int i : arr) {
            if (q.size() == k && q.peek() <= i) continue;
            if (q.size() == k) q.poll();
            q.add(i);
        }
        for (int i = k - 1; i >= 0; i--) ans[i] = q.poll();
        return ans;
    }
}
复制代码

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

class Solution {
    int k;
    public int[] smallestK(int[] arr, int _k) {
        k = _k;
        int n = arr.length;
        int[] ans = new int[k];
        if (k == 0) return ans;
        qsort(arr, 0, n - 1);
        for (int i = 0; i < k; i++) ans[i] = arr[i];
        return ans;
    }
    void qsort(int[] arr, int l, int r) {
        if (l >= r) return ;
        int i = l, j = r;
        int ridx = new Random().nextInt(r - l + 1) + l;
        swap(arr, ridx, l);
        int x = arr[l];
        while (i < j) {
            while (i < j && arr[j] >= x) j--;
            while (i < j && arr[i] <= x) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        // 集中答疑：因为题解是使用「基准点左侧」来进行描述（不包含基准点的意思），所以这里用的 k（写成 k - 1 也可以滴
        if (i > k) qsort(arr, l, i - 1);
        if (i < k) qsort(arr, i + 1, r);
    }
    void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
}
复制代码