0347._Top_K_Frequent_Elements.md

347. Top K Frequent Elements

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/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.

解题方案

思路 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], 
- count为2的数字有2和4，我们就令buckets[2] = [2,4]
- count为1的数字有3，我们就令buckets[1] = [3]


最后我们从bucktes的最后一个元素开始遍历，如果该元素不为初始化的'*'的话,我们就把当前元素（type list）的元素全部extend到res中去，最后返回res

时间复杂度为O(n)

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res, maps, buckets = [], collections.Counter(nums), ['*'] * (len(nums)+1)

        for key in maps.keys():
            count = maps.get(key)
            if buckets[count] == '*':
                buckets[count] = []
            buckets[count].append(key)
        i = len(nums)
        while len(res) < k and i >= 0:
            if buckets[i] != '*':
                res.extend(buckets[i])
            i -= 1
        return res

思路 2 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******

如果题目没有要求时间复杂度必须要优于o(nlgn)的话，下面这个解法更简单

class Solution:
    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':
        return [kk for kk, vv in collections.Counter(nums).most_common(k)]
        # return [kk for kk, vv in sorted(collections.Counter(nums).items(), key = lambda x: -x[1])][:k]