[每日一题] 第二十题:最小的k个数

题目描述

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

示例 1:

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

示例 2:

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

限制:

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

题解

方法一:使用 Arrays.sort() 方法

代码

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

        return result;
    }
}

时间复杂度

方法二:堆排序

比较直观的想法是使用堆数据结构来辅助得到最小的 K 个数,堆的性质是每次可以得到最大或最小的元素。我们可以使用一个大小为 K 的最大堆(大顶堆),将数组中的元素依次推入堆,当堆的大小超过 K 时,便将多余的元素从堆顶弹出。我们以数组 [5, 4, 1, 3, 6, 2, 9]k=3 为例展示元素入堆的过程,如下面动图所示:

这样,由于每次从堆顶弹出的数都是堆中最大的,最小的 K 个元素一定会留在堆里。 这样,把数组中的元素全部入堆之后,堆中剩下的 K 个元素就是最小的 K 个数了。

注意在动画中,我们并没有画出堆的内部结构,因为这部分内容并不重要,我们只需要知道堆每次会弹出最大的元素即可。在写代码的时候,我们使用的也是库函数中优先队列数据结构,如 Java 中的 priorityQueue。在面试中,我们不需要实现堆的内部结构,把数据结构使用好,会分析复杂度即可。

以下是题解代码。感谢评论区提醒,这里的代码可以做一些优化,如果当前数字不小于堆顶元素,数字可以直接丢掉,不如堆,下方的代码已更新:

public int[] getLeastNumbers(int[] arr, int k) {
    if (k == 0) {
        return new int[0];
    }
    // 使用一个最大堆(大顶堆)
    // Java 的 PriorityQueue 默认是小顶堆,添加 comparator 参数使其变成最大堆
    Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));

    for (int e : arr) {
        // 当前数字小于堆顶元素才会入堆
        if (heap.isEmpty() || heap.size() < k || e < heap.peek()) {
            heap.offer(e);
        }
        if (heap.size() > k) {
            heap.poll(); // 删除堆顶最大元素
        }
    }

    // 将堆中的元素存入数组
    int[] res = new int[heap.size()];
    int j = 0;
    for (int e : heap) {
        res[j++] = e;
    }
    return res;
}

复杂度

  • 空间复杂度:由于使用了一个大小为 K 的堆,空间复杂度为 O(N)
  • 时间复杂度:入堆和出堆的时间复杂度均为 O(logK),每个元素都需要进行一次入堆操作,故算法的时间复杂度为 O(n logK)。

来源

作者:nettee
链接:leetcode-cn.com/problems/zui-xiao-...
来源:力扣(LeetCode)

方法三:快排变形

Top K 问题的另一个解法就比较难想到,需要在平时有算法的积累,实际上,”查找第 K 大元素“是一类算法问题,称为选择问题。找到第 K 大的元素,或者是前 K 大的元素,有一个经典的 quick select(快速选择)算法。这个名字和 quick sort(快速排序)看起来很像,算法的思想野核快速排序相似,都是分治法的思想。

[每日一题] 第二十题:最小的k个数

这个 partition 操作是原地进行的,需要 O(N) 的时间,接下来,快速排序会递归的排序左右两侧的数据,而 quick select(快速选择)的算法不同之处在于,接下来只需要递归的选择一侧的数组,快速选择算法相当于一个”不完全“的快速排序,因为我们只需要知道最小的 k 个数是哪些,并不需要知道他们的顺序。

我们的目的是寻找最小的 k 个数,假设经过一次 partition 操作,枢纽元素位于下标 m,也就是说,左侧的数组有 m 个元素,是原数组中的最小的 m 个数。那么:

  • 若 k=m,我们就找到了最小的 k 个数,就是左侧的数据。
  • 若 k<m,则最小的 k 个数一定都在左侧数组中,我们只需要对左侧数组递归地 partition 即可。
  • 若 k>m,则左侧数组的 m 个数都属于最小的 k 个数,我们还需要在右侧数组中寻找最小的 k-m 个数,对右侧数组递归的 partition 即可。

这种方法需要多加领会思想,如果你对快速排序掌握得很好,那么稍加推导应该不难掌握 quick select 的要领。

以下是题解代码:

代码

public int[] getLeastNumbers(int[] arr, int k) {
    if (k == 0) {
        return new int[0];
    } else if (arr.length <= k) {
        return arr;
    }

    // 原地不断划分数组
    partitionArray(arr, 0, arr.length - 1, k);

    // 数组的前 k 个数此时就是最小的 k 个数,将其存入结果
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = arr[i];
    }
    return res;
}

void partitionArray(int[] arr, int lo, int hi, int k) {
    // 做一次 partition 操作
    int m = partition(arr, lo, hi);
    // 此时数组前 m 个数,就是最小的 m 个数
    if (k == m) {
        // 正好找到最小的 k(m) 个数
        return;
    } else if (k < m) {
        // 最小的 k 个数一定在前 m 个数中,递归划分
        partitionArray(arr, lo, m-1, k);
    } else {
        // 在右侧数组中寻找最小的 k-m 个数
        partitionArray(arr, m+1, hi, k);
    }
}

// partition 函数和快速排序中相同,具体可参考快速排序相关的资料
// 代码参考 Sedgewick 的《算法4》
int partition(int[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    int v = a[lo];
    while (true) { 
        while (a[++i] < v) {
            if (i == hi) {
                break;
            }
        }
        while (a[--j] > v) {
            if (j == lo) {
                break;
            }
        }

        if (i >= j) {
            break;
        }
        swap(a, i, j);
    }
    swap(a, lo, j);

    // a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
    return j;
}

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

上述代码中需要注意一个细节(评论区有好几个小伙伴问到,这里补充说明一下):

partitionArray 函数中,两次递归调用传入的参数为什么都是 k?特别是第二个调用,我们在右侧数组中寻找最小的 k-m 个数,但是对于整个数组而言,这是最小的 k 个数。所以说,函数调用传入的参数应该为 k。

该代码的成绩还是非常好的:

复杂度

  • 空间复杂度 O(1),不需要额外空间。
  • 时间复杂度的分析方法和快速排序类似。由于快速选择只需要递归一边的数组,时间复杂度小于快速排序,期望时间复杂度为 O(n),最坏情况下的时间复杂度为 O(n^2)。

两种方法的优劣性比较

在面试中,另一个常常问的问题就是这两种方法有何优劣。看起来分治法的快速选择算法的时间、空间复杂度都优于使用堆的方法,但是要注意到快速选择算法的几点局限性:

第一,算法需要修改原数组,如果原数组不能修改的话,还需要拷贝一份数组,空间复杂度就上去了。

第二,算法需要保存所有的数据。如果把数据看成输入流的话,使用堆的方法是来一个处理一个,不需要保存数据,只需要保存 k 个元素的最大堆。而快速选择的方法需要先保存下来所有的数据,再运行算法。当数据量非常大的时候,甚至内存都放不下的时候,就麻烦了。所以当数据量大的时候还是用基于堆的方法比较好。

来源

作者:nettee
链接:leetcode-cn.com/problems/zui-xiao-...
来源:力扣(LeetCode)

来源

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/zui-xiao-...

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!