当前位置:   article > 正文

每日一道leetcode(python)347. 前 K 个高频元素_python给你一个整数数组nums和一个整数k,返回其中出现频率前k

python给你一个整数数组nums和一个整数k,返回其中出现频率前k

每日一道leetcode(python)347. 前 K 个高频元素

2021-08-13

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

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

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

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的
 
进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/top-k-frequent-elements
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

思路一

  • 调用库函数collections计数,在返回数值最大的前K个元素
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        import collections,heapq # 导入库函数
        count = collections.Counter(nums)  
        return heapq.nlargest(k, count.keys(), key=count.get)
  • 1
  • 2
  • 3
  • 4
  • 5

思路二

  • 哈希表,利用字典存储每个元素出现的次数。
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic1 = {}
        n = len(nums)
        for i in range(n):
            dic1[nums[i]] = dic1.get(nums[i], 0) + 1
        res = []
        for j in range(k): # 返回字典中value最大值对应的key
            res.append(max(dic1, key = dic1.get))
            dic1[res[j]] = 0 # 归零,相当于剔除最大值,继续求第二最大值
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/花生_TL007/article/detail/72795
推荐阅读
相关标签
  

闽ICP备14008679号