找前k大个数的方法

短命女 2024-03-27 18:49 142阅读 0赞

#### 找前k大个数的方法 ####

*  1. 小堆法
 *   *  步骤
     *  复杂度
 *  2. 快速选择算法
 *   *  步骤
     *  复杂度
 *  3. 分治法
 *   *  步骤
     *  复杂度
 *  4. 排序后取前k个元素
 *   *  复杂度

## 1. 小堆法 ##

小根堆是一种数据结构，其中每个节点的值都小于或等于其子节点的值。

### 步骤 ###

1.  维护一个包含k个元素的小根堆（初始状态为空）。
2.  遍历数组中的元素，将它们逐个添加到堆中。
3.  如果堆的大小超过了k，就弹出堆顶元素（最小值），保持堆的大小为k。
4.  遍历完所有元素后，堆中包含的就是前k大的数。

### 复杂度 ###

在这个过程中，每次插入或弹出元素都需要对堆进行调整，保持其小根堆的性质。插入和弹出操作的时间复杂度是O(log k)。

总的时间复杂度是O(n log k)，其中n是数组的长度，k是要找出的前k大的数的个数。

这种方法适用于当n很大但k相对较小的情况，因为它只需要维护一个大小为k的堆，而不需要对整个数组进行排序。

## 2. 快速选择算法 ##

快速选择算法类似于快速排序，它可以在平均情况下以线性时间复杂度找到第k大的元素。

### 步骤 ###

该算法的思想是通过随机选取一个元素作为"基准"，将数组分成两部分，一部分大于基准，另一部分小于基准，然后递归地在较大或较小的部分继续寻找第k大的元素。

### 复杂度 ###

平均情况下，快速选择算法的时间复杂度是O(n)，因为它以线性时间找到第k大的元素。最坏情况下的时间复杂度为O(n^2)，但通常情况下会更快。

## 3. 分治法 ##

### 步骤 ###

分治法是将数组分成若干个子数组，然后递归地找出每个子数组的前k大的数，最后合并结果。

### 复杂度 ###

分治法的时间复杂度取决于具体的实现，通常在平均情况下为O(n)。这种方法可以用于处理更复杂的选择问题，而不仅仅是前k大的数。

## 4. 排序后取前k个元素 ##

将数组排序，然后取前k个元素。

如果k相对较小，可以使用部分排序的方法（例如堆排序、快速排序等）来优化时间复杂度。

### 复杂度 ###

如果需要找出前k大的数，最简单的方法是对整个数组进行排序，然后取前k个元素。这种方法的时间复杂度是O(n log n)，其中n是数组的长度。

如果使用部分排序，例如堆排序，时间复杂度为O(n log k)，其中n是数组的长度，k是前k大的数的个数。这种方法适用于k相对较小的情况，以减少不必要的排序开销。

发表评论取消回复

表情：

评论列表（有 0 条评论，142人围观）

还没有评论，来说两句吧...

相关阅读

相关找出数组中第k大的数

package com.threeTop.www; /** * 找出数组中第k大的数 * @author wjgs ...

╰半夏微凉°/ 2024年04月17日 14:47/ 0 赞/ 151 阅读

相关找前k大个数的方法

找前k大个数的方法 1. 小堆法步骤复杂度 2. 快速选择算法步骤复杂度 3. 分治法

短命女/ 2024年03月27日 18:49/ 0 赞/ 143 阅读

相关 Python求解Top K问题：如何从一个数组中找出前K个最大或最小的数？

Python求解Top K问题：如何从一个数组中找出前K个最大或最小的数？在实际的开发和数据分析过程中，Top K问题是一类经常遇到的问题。例如，在排行榜中找出得分最高的前

痛定思痛。/ 2024年03月24日 10:34/ 0 赞/ 160 阅读

相关快排思想找1亿个数的前100个最大值

从一亿个随机数里寻找前100个最大的数，如果根据常规的快速排序排完一亿个数，再取前100个数，那么耗时11~12s（VM内存设置：-Xms256m -Xmx1024m），因为

绝地灬酷狼/ 2023年06月07日 10:58/ 0 赞/ 93 阅读

相关输出前k大的数（分治算法）

给定一个数组，统计前k大的数并把前k大的数从小到大输出来。输入： 10 4 5 6 9 8 7 1 2 3 0 5 输出： 9 8 7 6

刺骨的言语ヽ痛彻心扉/ 2023年03月01日 09:28/ 0 赞/ 42 阅读

相关 347. Top K Frequent Elements(前k个众数）

给定一个非空的整数数组，返回k个最频繁的元素范例1：输入： nums = \[1,1,1,2,2,3\]，k = 2 输出：\[1,2\] 范例2：输

ゞ浴缸里的玫瑰/ 2023年02月13日 05:47/ 0 赞/ 40 阅读

相关找出数组中的第K大的数或者第K小的数

class Solution { public: int findKthLargest(vector<int>& res, int k)

本是古典何须时尚/ 2022年12月31日 01:25/ 0 赞/ 266 阅读

相关输出前k大的数

输出前k大的数题目给定一个数组，统计前k大的数并且把这k个数从大到小输出。输入第一行包含一个整数n，表示数组的大小。n < 100000。第二

Love The Way You Lie/ 2022年10月28日 14:28/ 0 赞/ 227 阅读

相关从100万个数中找出最大的前100个数

[https://blog.csdn.net/cslbupt/article/details/65935577][https_blog.csdn.net_cslbupt_art

谁践踏了优雅/ 2022年05月10日 23:46/ 0 赞/ 300 阅读

相关如何在 10 亿数中找出前 1000 大的数

点击蓝色“五分钟学算法”关注我哟加个“星标”，一起学算法 ![640?wx\_fmt=jpeg][640_wx_fmt_jpeg] 作者 | channingbreez

秒速五厘米/ 2021年12月19日 01:51/ 0 赞/ 324 阅读