347. Top K Frequent Elements

问题描述

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.

思路

loop一遍nums，把每个数字和对应的出现次数存进一个dict
把dict的key和value位置对换。 注意，避免把对换后的数据存在另一个dictionary中，因为不同的数字可能出现的次数是一样的，会被覆盖
之后根据频次排序，将频次排在前k个的对应数字存进一个数组并返回即可

    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        dict = {}
        for i in nums:
            if i in dict:
                dict[i] += 1
            else:
                dict[i] = 1
        revDict = []

        for j in dict.keys():
            revDict.append([dict.get(j), j])

        sortByH = sorted(revDict, key=lambda s: s[0])
        ans = []
        while k and sortByH:
            ans.append(sortByH.pop()[1])
            k -= 1
        return ans