最小的k个数

题目描述

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

示例 1：

1 2	输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]

示例 2：

1 2	输入：arr = [0,1,2,1], k = 1 输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

题目链接

Leetcode

题目解答

解法一

按照题目要求，最直观的处理方式就是先排序，然后取排序后数组的前k个元素组成新数组返回即可。

时间复杂度:$O(n\log{}n)$ 空间复杂度:$O(\log{}n)$

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

执行用时：7 ms, 在所有 Java 提交中击败了72.51%的用户
内存消耗：39.7 MB, 在所有 Java 提交中击败了68.57%的用户

解法二

题目要求找出最小的k个元素，我们可以使用一个大根堆实时维护数组中前k小的元素，初始化堆的时候，先直接把数组前k个元素加入堆中，从第k+1个元素开始，把元素值与堆顶值做比较，如果比堆顶值小，就把堆顶元素弹出，把数组元素加入到堆中。数组遍历结束的时候，用堆中的元素组成的新数据就是所需结果。

时间复杂度:$O(n\log{}k)$ 空间复杂度:$O(\log{}k)$

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        if (k == 0) {
            return res;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        for (int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll();
        }
        return res;
    }
}

执行用时：20 ms, 在所有 Java 提交中击败了33.19%的用户
内存消耗：39.5 MB, 在所有 Java 提交中击败了88.20%的用户

解法三

使用分治递归把大问题划分为子问题求解，借鉴快速排序的划分函数，我们可以选取一个中间值target把数组划分为两部分，同时调整两部分的值，使得左边部分的元素值都小于target，右边部分的元素值都大于target。递归的过程中，我们只需要处理包含前k个小元素的部分，当我们处理到的元素下标是第k个元素时，划分结束，原数组的前k个元素就是整个数组中的前k个小元素。

时间复杂度:$O(n)$ 空间复杂度:$O(\log{}n)$

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        process(arr, 0, arr.length - 1, k);
        return Arrays.copyOfRange(arr, 0, k);
    }

    public void process(int[] arr, int l, int r, int k) {
        if (k == 0) return;
        int i = l - 1, j = r + 1, target = arr[(l + r) >> 1];
        while (i < j) {
            do i++; while (arr[i] < target);
            do j--; while (arr[j] > target);
            if (i < j) swap(arr, i, j);
        }
        if (j + 1 == k) {
            return;
        } else if (j + 1 > k) {
            process(arr, l, j, k);
        } else {
            process(arr, j + 1, r, k);
        }
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.7 MB, 在所有 Java 提交中击败了74.27%的用户