[LeetCode]40.最小的k个数(TopK问题。通过维护堆、优先队列、快排思想等解决方法)

本文主要是介绍[LeetCode]40.最小的k个数(TopK问题。通过维护堆、优先队列、快排思想等解决方法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最小的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




思路

1.暴力法,先对数组进行排序(各种排序方法),再取出前k个数。

public int[] getLeastNumbers(int[] arr, int k) {Arrays.sort(arr);int[] ints = new int[k];for (int i = 0; i < k - 1; i++) {ints[i]=arr[i];}return ints;
}

2.建立大根堆解决前K小问题.(小根堆解决前K大问题)。维护一个大根堆,若堆的大小小于K,将当前值放入队中。否则判断当前值与堆顶元素的大小,如果当前值小于堆顶元素,再将当前值放入堆中,每放入一个值后,再要调整成为大根堆。

    public  int[] getLeastNumbers(int[] arr,int k) {if (k == 0 || arr.length == 0) {return new int[0];}int[] ints = Arrays.copyOf(arr, k);//构建k个数的大根堆,堆顶为最大的数,for循环确保每个子堆都是大根堆,至少有ints.length/ 2个子堆。for (int i =ints.length/ 2; i >= 0; i--) {setHeap(ints, i, k);}//每次取数组中剩下的数与堆顶的数比较for (int i = k; i <arr.length; i++) {//如果数组中的数比堆顶的数小,则放入堆顶,再构建一次大根堆if (ints[0]>arr[i]){ints[0]=arr[i];setHeap(ints,0,k);}}return ints;}public  void  setHeap(int [] array,int parent,int length){int temp=array[parent];int child=parent*2+1;//循环判断父节点的值是否小于子节点,是则替换while (length>child){//取出子节点中较大的数的索引if(child+1<length && array[child]<array[child+1]){child++;}//如果父节点值大于子节点则不用交换值if(temp>=array[child]){break;}//交换父节点和子节点的值array[parent]=array[child];parent=child;child=2*child+1;}array[parent]=temp;}

3.使用优先队列代替堆,优先队列的实现原理与大根堆/小根堆相同。效率不如手写堆。(也许是调用库函数会加载其他东西)

public int[] getLeastNumbers(int[] arr, int k) {if ( k==0 || arr.length==0){return new int[0];}PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2-o1);//优先队列默认为升序排列,重写compare方法为降序排列。使用lombda表示,等价于以下代码
//        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2-o1;
//            }
//        });for (int i : arr) {if (queue.size()<k){queue.offer(i);}else if (queue.peek()>i){ //当优先队列满k个后,取最大值和待放入的值比较,如果待放入值小,则放入。queue.poll();queue.offer(i);}}int[] ints = new int[queue.size()];for (int i = 0; i < ints.length; i++) {ints[i]=queue.poll();}return ints;}

4.快速排序思想,但是不对数组完全排序,只需要有选择性的分段排序,当确定基准等于K时,则K左边的数都比k小。右边的数不需要处理。

    public int[] getLeastNumbers(int[] arr, int k) {if (k == 0 || arr.length == 0) {return new int[0];}//k-1为我们要找的基准的下标。return quickSort(arr, 0, arr.length - 1, k - 1);}public int[] quickSort(int[] arr, int left, int right, int k) {// 对数组进行分割,取出下次分割的基准标号int division = division(arr, left, right);//如果基准与k正好相等,则返回k左边的部分。if (division == k) {return Arrays.copyOf(arr, k + 1);}// 如果k在基准的右边,则对右段进行递归排序。// 如果k在基准的坐边,则对左段进行递归排序。return division < k ? quickSort(arr, division + 1, right, k) : quickSort(arr, left, division - 1, k);}public int division(int[] list, int left, int right) {// 以最左边的数(left)为基准int base = list[left];while (left < right) {// 从序列右端开始,向左遍历,直到找到小于base的数while (left < right && list[right] >= base) {right--;}// 找到了比base小的元素,将这个元素放到最左边的位置list[left] = list[right];// 从序列左端开始,向右遍历,直到找到大于base的数while (left < right && list[left] <= base) {left++;}// 找到了比base大的元素,将这个元素放到最右边的位置list[right] = list[left];}// 最后将base放到left位置。都比此时,left位置的左侧数值应该left小;// 而left位置的右侧数值应该都比left大。list[left] = base;return left;}

5.题目中规定数字不大于一万,可以使用频次数字处理,然后遍历频次数组,获取前K个数。

public int[] getLeastNumbers(int[] arr, int k) {if (k == 0 || arr.length == 0) {return new int[0];}// 统计每个数字出现的次数int[] hash = new int[10001];for (int num : arr) {hash[num]++;}int[] ans = new int[k];int count=0;for (int num = 0; num < hash.length; num++) {if (count == k) {break;}//从频次数组中取出前k个数。while (hash[num]>0 && k>count){ans[count++]=num;hash[num]--;}}return ans;
}

这篇关于[LeetCode]40.最小的k个数(TopK问题。通过维护堆、优先队列、快排思想等解决方法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/826948

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

如何解决线上平台抽佣高 线下门店客流少的痛点!

目前,许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流,但其费用昂贵。鉴于此,众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台,但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下,商家之间的合作网络逐渐成为一种有效的解决方案,通过资源和客户基础的共享,实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例,该平台融合了环保消费积分系统,在短

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监