LeetCode: 数组topK问题总结 - Python

LeetCode: 数组topK问题总结问题描述今天来总结一下数组求topK的问题其实这个问题不难在一次面试中我错误的把前K个小的数理解成了前K个有序小的数了也许机会就失之交臂了哈哈。现在看看topK的问题都有哪些1LeetCode 215. 数组中的第K个最大元素2剑指 Offer 40. 最小的k个数3LeetCode: 面试题 17.14. 最小K个数4LeetCode: 347. 前 K 个高频元素5LeetCode: 658. 找到 K 个最接近的元素6快速排序问题分析解决这类题目的一般套路是1使用快速排序法找到第K个数也就是第K个位置归位如果是求最大的第K个数就是找n-k的位置。2如果是求最小K个数就遍历数组输出所有小于K的数即可。3思路清晰了现在就看看代码实现吧。LeetCode 215. 数组中的第K个最大元素 - Python3实现[1]# Time :2023/09/10# Author :# 快速排序classSolution:deffindKthLargest(self,nums:List[int],k:int)-int:pivotrandom.choice(nums)left[vforvinnumsifvpivot]mid[vforvinnumsifvpivot]right[vforvinnumsifvpivot]L,Mlen(left),len(mid)ifkL:returnself.findKthLargest(left,k)elifkLM:returnpivotelse:returnself.findKthLargest(right,k-L-M)剑指 Offer 40or面试题 17.14.最小K个数# Time :2023/09/10# Author :# 快速排序 优秀代码参考 [1]classSolution:defpartition(self,nums,left,right):# 左右分区pivotnums[left]# 初始化一个待比较数据i,jleft,rightwhileij:whileijandnums[j]pivot:# 从后往前查找直到找到一个比pivot更小的数j-1nums[i]nums[j]# 将更小的数放入左边whileijandnums[i]pivot:# 从前往后找直到找到一个比pivot更大的数i1nums[j]nums[i]# 将更大的数放入右边# 循环结束i与j相等nums[i]pivot# 待比较数据放入最终位置returni# 返回待比较数据最终位置deftopk_split(self,nums,k,left,right):# 寻找到第k个数停止递归使得nums数组中index左边是前k个小的数index右边是后面n-k个大的数ifleftright:indexself.partition(nums,left,right)ifindexk:# 找到了 第 K 个位置returnelifindexk:self.topk_split(nums,k,index1,right)else:self.topk_split(nums,k,left,index-1)defgetLeastNumbers(self,arr:List[int],k:int)-List[int]:self.topk_split(arr,k,0,len(arr)-1)returnarr[:k]相关参考[1] 优秀代码参考基于快排的所有TopK问题简单python模板声明总结学习有问题或不当之处可以批评指正哦谢谢。