347. Top K Frequent Elements

347. Top K Frequent Elements

难度: Medium

刷题内容

原题连接

内容描述

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.

解题方案

思路 1
- 时间复杂度: O(N)- 空间复杂度: O(N)

题目自己限定了k一定是合法的,所以不可能出现两个数字出现频率相同的情况

思路就是我们先把对应的数字和其出现频次放到一个map里面,然后对这个maps里面的value()集合做一个for loop,这样我们就可以得到一个list,
list里面的每一个元素代表的就是count为该对应index的key(即数字)的集合

例如:
```
k = 2
nums = [1,1,1,2,2,3,4,4]时,

我们的maps就是{1: 3, 2: 2, 3: 1},
然后我们新建一个buckets,

  • count为3的数字有1,我们就令bucktes[3] = [1],
top Created with Sketch.