尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
Python 找出数组中最大的 k 个元素(Find k largest elements in an array)
如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定一个数组arr[]和一个整数k任务是找出给定数组中最大的 k 个元素。输出数组中的元素应按降序排列。例如输入[1, 23, 12, 9, 30, 2, 50]k 3输出[ 50, 30, 23]输入[11, 5, 12, 9, 44, 17, 2]k 2输出[ 44, 17]【朴素方法】使用排序其思路是将输入数组按降序排列使数组中的前k 个元素成为最大的k 个元素。# Python program to find k largest elements in an# array using sortingdef kLargest(arr, k):# sort the given array in descending orderarr.sort(reverseTrue)# store the first k elements in result listres arr[:k]return resif __name__ __main__:arr [1, 23, 12, 9, 30, 2, 50]k 3res kLargest(arr, k)print( .join(map(str, res)))输出50 30 23时间复杂度O(n * log n)辅助空间O(1)【预期方法】使用优先级队列最小堆其思路是在遍历数组的过程中每一步都记录下最大的 k 个元素。为此我们使用最小堆。首先将初始的 k 个元素插入最小堆。之后对于每个后续元素我们将其与堆顶元素进行比较。由于最小堆的堆顶元素是这 k 个元素中最小的如果当前元素大于堆顶元素则意味着堆顶元素不再是最大的 k 个元素之一。在这种情况下我们移除堆顶元素并插入更大的元素。完成整个遍历后堆将恰好包含数组中最大的 k 个元素。# Python program to find the k largest elements in the# array using min heapimport heapq# Function to find the k largest elements in the arraydef kLargest(arr, k):# Create a min-heap with the first k elementsminH arr[:k]heapq.heapify(minH)# Traverse the rest of the arrayfor x in arr[k:]:if x minH[0]:heapq.heapreplace(minH, x)res []# Min heap will contain only k# largest elementwhile minH:res.append(heapq.heappop(minH))# Reverse the result array, so that all# elements are in decreasing orderres.reverse()return resif __name__ __main__:arr [1, 23, 12, 9, 30, 2, 50]k 3res kLargest(arr, k)print( .join(map(str, res)))输出50 30 23时间复杂度O(n * log k)由于构建堆需要线性时间因此该方案可在 O(k (nk) Log K) 时间完成。辅助空间O(k)注意JavaScript 原生实现似乎不支持最小堆因此建议使用快速选择实现。【替代方法】使用快速选择算法其思路是利用快速排序的分区步骤在不重新排序整个数组的情况下找到数组中最大的 k 个元素。c 快速排序c 快速排序QuickSort_快速排序c代码-CSDN博客c语言 快速排序c语言 快速排序QuickSort_分区操作选择最后一个元素作为基准 c语言-CSDN博客python 快速排序Python 快速排序QuickSort_python实现快速排序-CSDN博客c# 快速排序C# 快速排序QuickSort-CSDN博客java 快速排序java 快速排序QuickSort_quicksort java-CSDN博客PHP 快速排序PHP 快速排序QuickSort-CSDN博客JavaScript快速排序JavaScript 快速排序QuickSort-CSDN博客在按降序对元素进行排序时分区步骤会重新排列元素将所有大于或等于选定基准元素通常是最后一个元素的元素放在基准元素的左侧将所有小于基准元素的元素放在基准元素的右侧并将基准元素置于其正确的排序位置。每次分区后我们将数组左侧部分包含所有大于或等于基准元素的元素的元素个数与 k进行比较左侧元素个数 k这意味着左侧部分的所有元素包括枢轴元素都是最大的 k 个元素。左侧元素个数 k这意味着最大的 k 个元素只存在于左侧子数组中因此我们在左侧子数组中递归搜索。左侧元素个数小于 k这意味着最大的 k 个元素包含了数组左侧的全部元素以及右侧的部分元素。因此我们将 k 减去左侧已覆盖的元素个数然后在右侧子数组中搜索。# Python program to find the k largest elements in the array# using partitioning step of quick sort# Function to partition the array around a pivotdef partition(arr, left, right):# Last element is chosen as a pivot.pivot arr[right]i leftfor j in range(left, right):# Elements greater than or equal to pivot# are placed in the left side of pivotif arr[j] pivot:arr[i], arr[j] arr[j], arr[i]i 1arr[i], arr[right] arr[right], arr[i]# The correct sorted position of the pivotreturn idef quickSelect(arr, left, right, k):if left right:pivotIdx partition(arr, left, right)# Count of all elements in the left partleftCnt pivotIdx - left 1# If leftCnt is equal to k, then we have# found the k largest elementif leftCnt k:return# Search in the left subarrayif leftCnt k:quickSelect(arr, left, pivotIdx - 1, k)# Reduce the k by number of elements already covered# and search in the right subarrayelse:quickSelect(arr, pivotIdx 1, right, k - leftCnt)def kLargest(arr, k):quickSelect(arr, 0, len(arr) - 1, k)# First k elements of the array, will be the largestres arr[:k]# Sort the result in descending orderres.sort(reverseTrue)return resif __name__ __main__:arr [1, 23, 12, 9, 30, 2, 50]k 3res kLargest(arr, k)print( .join(map(str, res)))输出50 30 23时间复杂度最坏情况下为O(n² )平均情况下为 O(n)。辅助空间O(n)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。
RELATED

相关推荐

深度学习(18)目标检测模型相关结构总结

深度学习(18)目标检测模型相关结构总结

深度学习(17)目标检测模型相关结构总结 总结模型中常用结构的含义与作用不定时更新 1. 常用术语👉自顶向下(Top-Down) 从“整体 → 局部”先有全局,再逐步细化 👉 自底向上(Bottom-U…

📅 2026/10/26 11:24:21
想降回iOS 14.3?downr1n完整降级避坑指南,让老iPhone重获新生

想降回iOS 14.3?downr1n完整降级避坑指南,让老iPhone重获新生

想降回iOS 14.3?downr1n完整降级避坑指南,让老iPhone重获新生 【免费下载链接】downr1n downgrade tethered checkm8 idevices ios 14, 15. 项目地址: https://gitcode.com/gh_mirrors/do/downr1n downr1n 是一个开源的 iOS 降级工具,…

📅 2026/10/23 9:10:05
单片机毕设项目:手动自动双模式智能台灯蓝牙监控系统设计 基于 51/STM32 单片机的光照人体感知照明装置开发(011904)

单片机毕设项目:手动自动双模式智能台灯蓝牙监控系统设计 基于 51/STM32 单片机的光照人体感知照明装置开发(011904)

博主介绍:✌️码农一枚 ,专注于大学生项目实战开发、讲解和毕业🚢文撰写修改等。全栈领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于嵌入式单片机,Java、小程序技术领域和毕业项目实战 ✌️…

📅 2026/10/24 16:34:31
MORE NEWS

更多资讯

📰

启动报Port 8088 was already in use?先查是谁占的

启动报Port 8088 was already in use?先查是谁占的 项目启动报 Port 8088 was already in use,意思很直白:这个端口已经有人占了。 先说原理:端口是"门牌号",一间房只住一个进程 端口就是一台机器上的门牌号…

📰

担心文档上云?本地运行的办公AI才敢放心用

单位上周开了个会,主题是"AI 提效",散会时领导补了一句:涉及客户资料的文档,不许往云端传。这话一出,会议室里本来跃跃欲试的同事全蔫了——大家平时用的那些在线 AI,文档一上传就不知道存哪儿去…

📰

先能用,再好用:从烂尾复盘到两周上线,全栈项目的‘原型—快速迭代‘方法论

先能用,再好用:从烂尾复盘到两周上线,全栈项目的“原型—快速迭代”方法论 全栈学习路径的文章已经很多了:怎么选技术栈、怎么搭环境、怎么记文档,几乎每个方向都有人写。但一个更扎心的问题很少有人正面讨论——为什…

📰

深度思考模式把 ARC-AGI-2 从 17.6% 拉到 45.1%:对照 Gemini 3 Pro 的三份能力评测,看‘会思考‘改写了哪些边界

深度思考模式把 ARC-AGI-2 从 17.6% 拉到 45.1%:对照 Gemini 3 Pro 的三份能力评测,看“会思考”改写了哪些边界 一、先说结论:变强的不是“知识”,而是“解法” 每次新模型发布,评测榜单都会涨几个点,大…

📰

1.c++入门篇

1.c中的关键字asmdoifreturntrycontinueautodoubleinlineshorttypedefforbooldynamic_castintsignedtypeidpublicbreakelselongsizeoftypenamethrowcaseenummutablestaticunionwchar_tcatchexplicitnamespacestatic_castunsigneddefaultcharexportnewstructusingfriendclassext…

📰

《江灯合声》:有可行的分框版,也仍可以选择连续鸣谢

武汉江岸区栎坡合唱团在免费节目册《江灯合声》中,以表格集中鸣谢资助者。各家共同要求改为独立小框,团里仍想保留表格。现有全名与支持事项清楚可见,双方此前未承诺具体排版。我支持保留表格。补充的试排材料让选择更具体:分框能…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬