当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.剑指offer.040.数组中最小的k个数

LeetCode.剑指offer.040.数组中最小的k个数

题目描述

《剑指offer》面试题40. 最小的k个数
https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

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

示例 1:

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

示例 2:

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

限制:
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000


相似题目

LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数
LeetCode.703.Kth Largest Element in a Stream 数据流中的第K大元素
LeetCode.378.Kth Smallest Element in a Sorted Matrix 有序矩阵中第K小的元素

LeetCode.347.Top K Frequent Elements 前K个高频元素
LeetCode.剑指offer.040.数组中最小的k个数
LeetCode.023.Merge k Sorted Lists 合并K个排序链表


解题过程

建立一个大小为K的最大堆,用数组的前K个元素初始化,然后从第K+1个元素开始:
如果大于堆顶,不可能是前K小的值,直接忽略
如果小于堆顶,将其加入堆中,调整堆,O(logk),然后把堆顶元素删除
这样最后最大堆剩下的k个元素就是前k小的数,堆顶是第k小的数
时间复杂度 O(Nlogk),空间复杂度 O(k)

  1. private static class SolutionV2020 {
  2. public int[] getLeastNumbers(int[] arr, int k) {
  3. if (0 == k) {
  4. return new int[] {};
  5. }
  6. // 最大堆
  7. PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((n1, n2) -> n2 - n1);
  8. for (int i = 0; i < arr.length; i++) {
  9. if (i < k) {
  10. priorityQueue.offer(arr[i]);
  11. } else if (arr[i] < priorityQueue.peek()) {
  12. priorityQueue.offer(arr[i]);
  13. priorityQueue.poll();
  14. }
  15. }
  16. return priorityQueue.stream().mapToInt(a -> a).toArray();
  17. }
  18. }

GitHub代码

algorithms/leetcode/offer/_040_KSmallElements.java
https://github.com/masikkk/algorithms/blob/master/leetcode/offer/_040_KSmallElements.java


上一篇 LeetCode.365.Water and Jug Problem 水壶问题

下一篇 LeetCode.409.Longest Palindrome 最长回文串

阅读
评论
443
阅读预计2分钟
创建日期 2020-03-20
修改日期 2020-03-20
类别

页面信息

location:
protocol: http:
host: devgou.com
hostname: devgou.com
origin: http://devgou.com
pathname: /article/LeetCode.Offer.040.KSmallElements/
href: http://devgou.com/article/LeetCode.Offer.040.KSmallElements/
document:
referrer:
navigator:
platform: Linux x86_64
userAgent: Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)

评论