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

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

网络异常,图片无法展示
|

题目描述



这是 LeetCode 上的 面试题 17.14. 最小K个数 ,难度为 中等


Tag : 「优先队列」、「堆」、「排序」


设计一个算法,找出数组中最小的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))


优先队列(小根堆)



一个直观的想法是使用「优先队列(小根堆)」,起始将所有元素放入堆中,然后再从堆中取出 kk 个元素并「顺序」构造答案。


网络异常,图片无法展示
|


代码:


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;
    }
}
复制代码


  • 时间复杂度:建堆复杂度为 O(n\log{n})O(nlogn),构造答案复杂度为 O(k\log{n})O(klogn)。整体复杂度为 O(n\log{n})O(nlogn)
  • 空间复杂度:O(n + k)O(n+k)


优先队列(大根堆)



在解法一中,我们将所有的原始都放入堆中,堆中元素最多有 nn 个,这导致了我们复杂度的上界为 O(n\log{n})O(nlogn)


而另外一个比较优秀的做法是,使用「优先队列(大根堆)」。


当处理到原始 arr[i]arr[i] 时,根据堆内元素个数,以及其与堆顶元素的关系分情况讨论:


  • 堆内元素不足 kk 个:直接将 arr[i]arr[i] 放入堆内;
  • 堆内元素为kk个:根据arr[i]arr[i]与堆顶元素的大小关系分情况讨论:
  • arr[i] >= heapToparr[i]>=heapToparr[i]arr[i] 不可能属于第 kk 小数(已有 kk 个元素在堆中),直接丢弃 arr[i]arr[i]
  • arr[i] < heapToparr[i]<heapToparr[i]arr[i] 可能属于第 kk 小数,弹出堆顶元素,并放入 arr[i]arr[i]


arrarr 被处理完,我们再使用堆中元素「逆序」构造答案。


网络异常,图片无法展示
|


代码:


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;
    }
}
复制代码


  • 时间复杂度:建堆复杂度为 O(n\log{k})O(nlogk),构造答案复杂度为 O(k\log{k})O(klogk)。整体复杂度为 O(n\log{k})O(nlogk)
  • 空间复杂度:O(k)O(k)


全排序



Java 中的 Arrays.sort 为综合排序实现。会根据数据规模、元素本身是否大致有序选择不同的排序实现。


因此一个比较省事的实现是先使用 Arrays.sort 进行排序,再构造答案。


网络异常,图片无法展示
|


代码:


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;
    }
}
复制代码


  • 时间复杂度:排序(假定 Arrays.sort 使用的是双轴快排实现)的复杂度为 O(n\log{n})O(nlogn);构造答案复杂度为 O(k)O(k)。整体复杂度为 O(n\log{n})O(nlogn)
  • 空间复杂度:O(\log{n} + k)O(logn+k)


快排数组划分



注意到题目要求「任意顺序返回这 kk 个数即可」,因此我们只需要确保前 kk 小的数都出现在下标为 [0, k)[0,k) 的位置即可。


利用「快速排序」的数组划分即可做到。


我们知道快排每次都会将小于等于基准值的值放到左边,将大于基准值的值放到右边。


因此我们可以通过判断基准点的下标 idxidxkk 的关系来确定过程是否结束:


  • idx < kidx<k:基准点左侧不足 kk 个,递归处理右边,让基准点下标右移;
  • idx > kidx>k:基准点左侧超过 kk 个,递归处理左边,让基准点下标左移;
  • idx = kidx=k:基准点左侧恰好 kk 个,输出基准点左侧元素。


网络异常,图片无法展示
|


代码:


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;
    }
}
复制代码


  • 时间复杂度:由于每次都会随机选择基准值,因此每次递归的数组平均长度为 n / 2n/2,那么划分数组操作的次数不会超过 2 * n2n。整体复杂度为 O(n)O(n)
  • 空间复杂度:O(\log{n})O(logn)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.面试题 17.14 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
7天前
|
Java
【LeetCode力扣】面试题 17.14. 最小K个数(top-k问题)
【LeetCode力扣】面试题 17.14. 最小K个数(top-k问题)
14 1
|
7天前
|
算法
leetcode代码记录(寻找两个正序数组的中位数
leetcode代码记录(寻找两个正序数组的中位数
13 2
|
7天前
|
索引
leetcode代码记录(最长重复子数组
leetcode代码记录(最长重复子数组
13 0
|
7天前
leetcode代码记录(两个数组的交集
leetcode代码记录(两个数组的交集
9 1
|
7天前
leetcode代码记录(最大子数组和
leetcode代码记录(最大子数组和
12 2
|
7天前
|
算法
【刷题】 leetcode 面试题 08.05.递归乘法
递归算法是一种在计算机科学和数学中广泛应用的解决问题的方法,其基本思想是利用问题的自我相似性,即将一个大问题分解为一个或多个相同或相似的小问题来解决。递归算法的核心在于函数(或过程)能够直接或间接地调用自身来求解问题的不同部分,直到达到基本情况(也称为基础案例或终止条件),这时可以直接得出答案而不必再进行递归调用。
25 4
【刷题】 leetcode 面试题 08.05.递归乘法
|
7天前
|
存储 算法 安全
【刷题】 leetcode 面试题 01.06 字符串压缩
来看效果: 非常好!!!过啦!!!
27 5
【刷题】 leetcode 面试题 01.06 字符串压缩
|
7天前
|
存储 算法
Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
给定一个无序整数数组和目标值,找出数组中和为目标值的两个数的下标。要求不重复且可按任意顺序返回。示例:输入nums = [2,7,11,15], target = 9,输出[0,1]。暴力解法时间复杂度O(n²),优化解法利用哈希表实现,时间复杂度O(n)。
22 0
|
7天前
|
索引
Leetcode 给定一个数组,给定一个数字。返回数组中可以相加得到指定数字的两个索引
Leetcode 给定一个数组,给定一个数字。返回数组中可以相加得到指定数字的两个索引
|
7天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
9 0