LeetCode 347. Top K Frequent Elements.jpg
LeetCode 347. Top K Frequent Elements
Description
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
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 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
思路
- 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值。
- 然后以元素出现的次数为值，统计该次数下出现的所有的元素。
- 从最大次数遍历到 1 次，若该次数下有元素出现，提取该次数下的所有元素到结果数组中，知道提取到 k 个元素为止。
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-04-09 12:37:36
# @Last Modified by: 何睿
# @Last Modified time: 2019-04-09 15:57:00
from collections import Counter
class Solution:
def topKFrequent(self, nums: [int], k: int) -> [int]:
# 桶
bucket = dict()
# 构建字典，键位数字，值为该数字出现过的次数
table = Counter(nums)
result, count = [], 0
# 以元素出现的次数位键，该次数下的所有元素构成的 List 为值
for num, times in table.items():
if times not in bucket: bucket[times] = []
bucket[times].append(num)
# 出现的最大次数
maxtime = max(table.values())
for time in range(maxtime, 0, -1):
# 如果该次数下有元素
if time in bucket:
# 提取当前次数下的所有元素到结果中
result.extend(bucket[time])
count += len(bucket[time])
if count == k: break
return result
