面试题 17.14. 最小K个数

系统管理员 2022-09-10 01:18 169阅读 0赞

#### [面试题 17.14. 最小K个数][17.14. _K] ####

难度：中等

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

**示例：**

输入： arr = [1,3,5,7,2,4,6,8], k = 4
    输出： [1,2,3,4]

**思路：**

> 优先级队列（大顶堆）

class Solution { 
    public:
        vector<int> smallestK(vector<int>& arr, int k) { 
            //1.直接排序
            //2.大顶堆(优先级队列)
            vector<int> res(k,0);
            if(0==k)
            { 
                return res;
            }
            priority_queue<int> Q;
            for(int i=0;i<k;i++)
            { 
                Q.push(arr[i]);
            }
            int Len=arr.size();
            for(int i=k;i<Len;i++)
            { 
                if(Q.top()>arr[i])
                { 
                    Q.pop();
                    Q.push(arr[i]);
                }
            }
            for(int i=0;i<k;i++)
            { 
                res[i]=Q.top();
                Q.pop();
            }
            return res;
        }
    };

[17.14. _K]: https://leetcode-cn.com/problems/smallest-k-lcci/

发表评论取消回复

表情：

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

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

相关阅读

相关最小K个数

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

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

相关面试题40. 最小的k个数

题目： [面试题40. 最小的k个数][40. _k] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_

矫情吗；*/ 2023年07月17日 11:17/ 0 赞/ 14 阅读

相关 leetcode 面试题40. 最小的k个数

思路：快排。不用完全排序，只要划分到某个值前面有k个数即可停止。 class Solution { public: vector<int>

傷城~/ 2023年07月17日 06:27/ 0 赞/ 10 阅读

相关面试题 17.14. 最小K个数

2021-09-03 LeetCode每日一题链接：[https://leetcode-cn.com/problems/smallest-k-lcci/][https_

╰+攻爆jí腚メ/ 2022年09月10日 03:18/ 0 赞/ 129 阅读

相关面试题 17.14. 最小K个数【分治法】

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

一时失言乱红尘/ 2022年09月10日 02:13/ 0 赞/ 164 阅读

相关面试题 17.14. 最小K个数

[面试题 17.14. 最小K个数][17.14. _K] 难度：中等设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。示例：输入：

系统管理员/ 2022年09月10日 01:18/ 0 赞/ 170 阅读

相关面试题30：最小的K个数

面试题30：最小的K个数题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,

不念不忘少年蓝@/ 2022年07月12日 05:51/ 0 赞/ 164 阅读

相关剑指offer面试题[30]-最小的k个数

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

客官°小女子只卖身不卖艺/ 2022年06月13日 10:44/ 0 赞/ 177 阅读

相关【剑指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 赞/ 206 阅读

相关【题 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 赞/ 238 阅读