leetcode 剑指 Offer 40. 最小的k个数

客官°小女子只卖身不卖艺 2023-03-01 12:57 2阅读 0赞

# 剑指 Offer 40. 最小的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

链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

# 解题 #

class Solution { 
        public int[] getLeastNumbers(int[] arr, int k) { 
            int[] ints = new int[k];
    
            if(k==0 || arr==null || arr.length < k )
                return ints;
    
    
            PriorityQueue<Integer> queue = new PriorityQueue<>(k,Collections.reverseOrder());
    
    
            for (int i = 0; i < arr.length; i++) { 
    
                if(i<k){ 
                    queue.offer(arr[i]);
                }else{ 
    
                    if(queue.peek()>arr[i]){ 
                        queue.poll();
                        queue.offer(arr[i]);
                    }
                }
    
            }
    
    
            for (int i = 0; i < k; i++) { 
                ints[i] = queue.poll();
            }
    
            return ints;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 剑指 Offer 40. 最小的k个数

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

客官°小女子只卖身不卖艺/ 2023年03月01日 12:57/ 0 赞/ 3 阅读

相关堆---剑指 Offer 40. 最小的k个数

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

野性酷女/ 2023年01月12日 15:58/ 0 赞/ 158 阅读

相关【剑指Offer】40. 最小的 K 个数

[NowCoder][] 解题思路快速选择复杂度：O(N) + O(1) 只有当允许修改数组元素时才可以使用快速排序的 partition()

妖狐艹你老母/ 2022年11月29日 12:18/ 0 赞/ 121 阅读

相关剑指 Offer 40. 最小的k个数

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

谁践踏了优雅/ 2022年11月21日 03:40/ 0 赞/ 178 阅读

相关剑指 Offer 40. 最小的k个数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

秒速五厘米/ 2022年10月29日 01:53/ 0 赞/ 136 阅读

相关【剑指offer】面试题40：最小的k个数

题目输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。 ps：题目只要求最小的k个数，没

系统管理员/ 2022年06月11日 04:44/ 0 赞/ 184 阅读

相关剑指offer 最小的k个数

1.题目描述输入n个数字，找出其中最小的k个数。注：有的还会要求保持原有的顺序输出 2.分析两种思路： 1）利用快排的思想，找到第k大的分界点。左边的

男娘i/ 2022年06月08日 09:38/ 0 赞/ 161 阅读

相关剑指offer 40.最小的 K 个数 python代码

题目寻找数组中的最小的k个数，也叫topk问题。 [牛客网测试地址][Link 1] 注意：牛客网的提交需要将最终的结果排序思路快速排序的 p

电玩女神/ 2022年05月25日 10:53/ 0 赞/ 169 阅读

相关《剑指offer》python ： 40 最小的k个数

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

﹏ヽ暗。殇╰゛Y/ 2022年05月17日 08:11/ 0 赞/ 149 阅读

相关【剑指offer】面试题40：最小的 k 个数

> 题目：输入n个整数，找出其中最小的 k 个数。例如输入 4, 5, 1, 6, 2, 7, 3, 8 这 8 个数字，则最小的 4 个数字是1, 2, 3, 4。牛客网

向右看齐/ 2022年03月27日 12:24/ 0 赞/ 220 阅读