【LeetCode】347. 前K个频繁出现的元素

频繁出现的元素"/>

【LeetCode】347. 前K个频繁出现的元素

问题描述

Given a non-empty array of integers, return the k most frequent elements.

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

给定一个非空的整数数组，返回k个最常见的元素。
注意:
你可以假设k总是有效的，1≤k≤元素的个数。
你的算法的时间复杂度必须优于O(n log n)，其中n是数组的大小。

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

Python 实现

实现一

最直接的解决思路，使用 dict 或者 map 统计元素出现的频率，然后选出出现频率最高的 K 个元素。

class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""if k == len(nums):return nums# Count the frequency with dictionary (key-value pair).dic = {}for num in nums:dic[num] = dic.get(num, 0) + 1# Sort in ascending order; compare frequency first, then compare the elements itself; reverse into descending order.sorted_list_pair = sorted(dic.items(), key=lambda kv:(kv[1], kv[0]), reverse=True)l = [element[0] for element in sorted_list_pair]return l[:k]

实现二：堆

题目要求算法的时间复杂度必须优于O(n log n)，出现 lon n 其实就提示了可以通过类似树这样的二分数据结构求解。在这里我们可以用元素的出现的频率作为 key 来构建堆，然后取出最大的 K 的结点即可。（这里直接使用 python 的库实现）

class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""# Method 2: heap.count = collections.Counter(nums)   return heapq.nlargest(k, count.keys(), key=count.get) 

链接：/