Python前K个高频元素怎么实现

发布时间:2021-11-26 09:26:05 作者:iii
来源:亿速云 阅读:217

本篇内容介绍了“Python前K个高频元素怎么实现”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

题目


给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示:

解题思路


思路:堆

首先审题,题目要求给定非空数组,求出频率前 k 高的元素。提示中说明,算法时间复杂度要优于 O(nlogn),又因为只需返回前 k 个频率最高的元素,那么我们借助堆的思路,对于频率 k 之后的不做处理,进而将时间复杂度优化到 O(nlogk)。

那么具体的做法如下:

具体代码实现如下(这里直接使用了 heapq 模块)。

from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        hash_map = {}

        # 哈希表统计元素出现频率
        for num in nums:
            if num not in hash_map:
                hash_map[num] = 0
            hash_map[num] += 1
        
        # 建立最小堆,存储频率最大的 k 个元素
        import heapq

        pq = []

        for key in hash_map:
            if len(pq) < k:
                heapq.heappush(pq, (hash_map[key],key))
            elif hash_map[key] > pq[0][0]:
                heapq.heapreplace(pq, (hash_map[key],key))

        # 取出最小堆中的元素
        res = []
        while pq:
            res.append(pq.pop()[1])

        return res


# nums = [3,0,1,0]
# nums = [4,1,-1,2,-1,2,3]
# k = 2

# solution = Solution()

# print(solution.topKFrequent(nums, k))

“Python前K个高频元素怎么实现”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!

推荐阅读:
  1. 堆的应用(1000个数据中找最大的前K个元素,堆排序)
  2. Python如何返回前K个最频繁的元素

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

python

上一篇:如何从PostgreSQL外部来查看内存

下一篇:C#如何实现基于Socket套接字的网络通信封装

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》