数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python 中 Top K 频繁元素
假设我们有一个非空整数数组。我们需要返回第 k 个最频繁的元素。例如，如果元素是 [1,1,1,1,2,2,3,3,3] 并且 k = 2，则结果将是
正式地说，函数应该：
- 如果存在 i、j、k
- 使得 arr[i] < arr[j] < arr[k]，其中 0 ≤ i < j < k ≤ n-1，则返回 true；否则返回 false。
为了解决这个问题，我们将遵循以下步骤：
- num_freq = 一个空映射，freq_list := 一个空映射
- 对于 nums 中的每个元素 i
- 如果 i 不在 num_freq 中，则 num_freq[i] := 1，否则将 num_freq[i] 加 1
- 对于 num_freq 映射中的每个键值对
- 如果值不在 freq_list 中，则 freq_list[value] := 一个包含 [key] 的列表，否则将 key 插入到 freq_list[value] 数组中
- res := 空列表
- 对于 i := 数字长度到 0
- 如果 i 在 freq_list 中，则将 freq_list[i] 的元素添加到 res 中
- 如果 res 的长度 >= k，则中断
- 返回结果
让我们看下面的实现来更好地理解：
示例
class Solution(object):
def topKFrequent(self, nums, k):
number_frequency = {}
frequency_list ={}
for i in nums:
if i not in number_frequency:
number_frequency[i] = 1
else:
number_frequency[i] += 1
for key,value in number_frequency.items():
if value not in frequency_list:
frequency_list[value] = [key]
else:
frequency_list[value].append(key)
result = []
for i in range(len(nums),0,-1):
if i in frequency_list:
result.extend(frequency_list[i])
if len(result) >=k:
break
return result
ob1 = Solution()
print(ob1.topKFrequent([1,1,1,1,2,2,3,3,3], 2))输入
[1,1,1,1,2,2,3,3,3] 2
输出
[1, 3]
更新于：2020年5月4日
2K+ 次浏览
广告