【数据结构与算法】找出最小的k个数:三路快速排序算法思想实现
2021/9/2 11:36:05
本文主要是介绍【数据结构与算法】找出最小的k个数:三路快速排序算法思想实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
找出最小的k个数:三路快速排序算法思想实现
Java
https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-san-lu-kuai-su-pai-x-5xro/
https://leetcode-cn.com/problems/smallest-k-lcci/solution/zui-xiao-kge-shu-san-lu-kuai-su-pai-xu-s-ns7y/
解题思路
本题类似找第K大的值的思路,同学们可以看看我关于那题的解法。同样的,找出最小的k个数也可以用快速排序算法的思路来解题。因为快速排序算法的隔断(partition)是排序好之后的位置固定不变了的,然后在这之前的是小于隔断的值,在这之后是大于隔断的值,那找出最小的k个数不就通过快速排序算法的隔断找到k的位置,然后返回在这之前的值组成的数组就行。
首先同样的,确保最小的k个数在数组中能找到,因为我这边使用的三路快速排序算法(对全部一样的数值的数组有速度优势),需要传回两个值,Java不支持多变量返回,我就直接写在一个函数里了,首先是初始化好相关变量,约定好隔断:V,(l,tl)<V,[tl,i)=V,[i,tg]未处理,(tg,r)>V,然后遍历[l,r),把相对应的元素放置到对应位置,最后处理隔断V,处理好之后就变成了[l,tl)<V, [tg,r)>V, [tl,tg) = V,这样,我们再判断k在哪个区间,如果是在等于V的区间,V是已经排好序了的,那就可以直接返回,在小于V的区间就调整r值后再次找隔断,同理大于V则调整l之后再调整,这样一步一步就能得到k处的元素值。找到K所在的位置之后,小于它的元素就都在它前面了,直接复制到新数组返回就好了。
对三路快速排序算法不太了解的同学可以去了解一下,这边双路应该也是可以实现的。
代码
class Solution { public int[] getLeastNumbers(int[] arr, int k) { if(k>=arr.length){ return arr; } Random random = new Random(); int l = 0,r = arr.length; // [l,r) while (true){ int rd = random.nextInt(r-l)+l; swap(arr,rd,l); // (l,tl)<V,(tg,r)>V,[i,tg]未处理,[tl,i) = V int i=l+1,tl = l+1,tg=r-1; while (i<=tg){ if(arr[i]>arr[l]){ swap(arr,tg,i); tg--; }else if(arr[i]<arr[l]){ swap(arr,tl,i); tl++; i++; }else { i++; } } tl--; swap(arr,tl,l); // [l,tl)<V,(tg,r)>V,[tl,tg] = V tg++; // [l,tl)<V,[tg,r)>V,[tl,tg) = V if(k>=tl&&k<=tg){ return Arrays.copyOf(arr,k); }else if(k<tl){ r = tl; }else { l = tg; } } } private void swap(int[] arr,int i,int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }
这篇关于【数据结构与算法】找出最小的k个数:三路快速排序算法思想实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?