面试题 17.14. 最小K个数

系统管理员 2022-09-10 01:18 157阅读 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 条评论，157人围观）

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

相关阅读

相关最小K个数

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

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

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

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

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

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

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

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

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

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

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

相关面试题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 赞/ 153 阅读

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

相关【面试题】剑指offer30--最小的k个数

输入n个整数，求出最小的k个数。使用简单的方法，对这组数进行升序排序，可以找到前k个数字代码实现： include<iostream> using n

ゝ一世哀愁。/ 2022年06月12日 02:09/ 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 赞/ 184 阅读

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

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