Given a non-empty array of integers, return the k most frequent elements.
返回第k个最常见的元素
返回元素出现个数最多的k个数
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(nlog n), where n is the array’s size.
- 您可以假设k始终有效，1≤k≤唯一元素的数量。 算法的时间复杂度必须优于O（n log n），其中n是数组的大小。
python实践
#!/usr/bin/env python
# _*_ coding:utf-8 _*_
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
# 使用桶排序的思想
# 1. 定义一个桶， 初始化为0
tub = [0]*(max(nums)+1)
# 2.如果nums的长度为1，直接输出
if len(nums) == 1:
return nums
for c in nums:
tub[c] += 1
print(tub)
j = 0
l = []
while j < k:
l.append(tub.index(max(tub)))
j += 1
tub[tub.index(max(tub))] = 0
print(l)
return l
if __name__ == '__main__':
nums = [1,1,1,2,2,3333333]
k = 2
Solution().topKFrequent(nums, k)
- 此方法出问题
