Leetcode 最小K个数

ゝ一世哀愁。 2022-09-10 03:14 160阅读 0赞

## 题目重述 ##

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/smallest-k-lcci  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 思路 ##

利用堆，即经典TOP-K问题  
这里使用Java的优先队列，利用其内部的堆排序，并改写使用大顶堆

## Java实现 ##

class Solution {
        
        public int[] smallestK(int[] arr, int k) {
        
            if(k==0){
        
                return new int[0];
            }
            Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
        
                @Override
                public int compare(Integer o1, Integer o2) {
        
                    return o2 - o1;
                }
            });
            for (int i = 0; i < arr.length; i++) {
        
                if(queue.size()<k){
        
                    queue.add(arr[i]);
                }else{
        
                    if(queue.peek()>arr[i]){
        
                        queue.poll();
                        queue.add(arr[i]);
                    }
                }
            }
            int[] result = new int[queue.size()];
            int len = queue.size();
            for (int i = 0; i < len; i++) {
        
                result[i] = queue.poll();
            }
            return result;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关最小K个数

[14天阅读挑战赛][14] 目录最小K个数方法一方法二 -------------------- 最小K个数设计一个算法，找出数组中最小的k个数

阳光穿透心脏的1/2处/ 2023年10月10日 15:13/ 0 赞/ 77 阅读

相关 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 赞/ 4 阅读

相关 Leetcode 最小K个数

题目重述设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。示例：输入： arr = [1,3,5,7,2,4,6,8], k = 4

ゝ一世哀愁。/ 2022年09月10日 03:14/ 0 赞/ 161 阅读

相关求最小的k个数

文章目录求最小的k个数 1.题目描述 2.题目链接 3.解题方法求最小的k个数 1.题目描述 ![在这里插

怼烎@/ 2022年08月30日 04:29/ 0 赞/ 181 阅读

相关最小的k个数

题目描述：查找最小的K个数题目：输入n个整数，输出其中最小的K个数例如，输入1、2、3、4、5、6、7、8这8个数字，则最小的4个数字为1、2、3、4。解题思路

左手的ㄟ右手/ 2022年08月20日 11:27/ 0 赞/ 174 阅读

相关寻找最小的k个数

寻找最小的k个数 1. 题目描述在一个长度为n的数组中，寻找最小的k个数。（最大的k个数解法类似） 2. 排序法想法比较简

绝地灬酷狼/ 2022年08月05日 17:59/ 0 赞/ 166 阅读

相关最小k个数 java

最小k个数 java 题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 > 代码

Love The Way You Lie/ 2022年05月12日 13:38/ 0 赞/ 194 阅读

相关最小的K个数

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ 题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4

谁借莪１个温暖的怀抱￠/ 2022年03月20日 03:24/ 0 赞/ 211 阅读

相关最小的K个数

时间限制：1秒空间限制：32768K 热度指数：363913 本题知识点：数组算法知识视频讲解题目描述输入n个整数，找出其中最小的K个数。例如输入4,

比眉伴天荒/ 2022年03月09日 10:46/ 0 赞/ 216 阅读

相关【题 40】最小k个数

【题目】输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。【思路】 1 排序，位于前k个

朴灿烈づ我的快乐病毒、/ 2022年03月08日 10:58/ 0 赞/ 216 阅读