[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

相关文章

SQL中如何添加数据(常见方法及示例)

《SQL中如何添加数据(常见方法及示例)》SQL全称为StructuredQueryLanguage,是一种用于管理关系数据库的标准编程语言,下面给大家介绍SQL中如何添加数据,感兴趣的朋友一起看看吧... 目录在mysql中,有多种方法可以添加数据。以下是一些常见的方法及其示例。1. 使用INSERT I

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

SQL Server配置管理器无法打开的四种解决方法

《SQLServer配置管理器无法打开的四种解决方法》本文总结了SQLServer配置管理器无法打开的四种解决方法,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录方法一:桌面图标进入方法二:运行窗口进入检查版本号对照表php方法三:查找文件路径方法四:检查 S

MyBatis-Plus 中 nested() 与 and() 方法详解(最佳实践场景)

《MyBatis-Plus中nested()与and()方法详解(最佳实践场景)》在MyBatis-Plus的条件构造器中,nested()和and()都是用于构建复杂查询条件的关键方法,但... 目录MyBATis-Plus 中nested()与and()方法详解一、核心区别对比二、方法详解1.and()

golang中reflect包的常用方法

《golang中reflect包的常用方法》Go反射reflect包提供类型和值方法,用于获取类型信息、访问字段、调用方法等,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值... 目录reflect包方法总结类型 (Type) 方法值 (Value) 方法reflect包方法总结