leetcode347-- Top K Frequent Elements

leetcode347-- 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.



解法

先不讲效率的话,最容易想的就是遍历一次建立一个字典,然后再找出前topk的,根据字典的排序。

如下


class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        dic = {}
        
        for x in nums:
            if x not in dic:
                dic[x] = 1
            else:
                dic[x] += 1
        
        ret = sorted(dic.items(), key=lambda x: x[1], reverse=True)

        return [x[0] for x in ret[:k]]

得到dic之后也可以使用桶排序,即根据出现的次数,然后把它放到对应的桶里

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        dic = {}
        
        for x in nums:
            if x not in dic:
                dic[x] = 1
            else:
                dic[x] += 1
        
        # 接下来也可以用桶排序,即根据出现的次数,但是同一个次数的可能不止一个,所以要一个二维的
        
        bucket = [[] for _ in range(len(nums))] 
        
        for key, value in dic.items():
            bucket[value-1].append(key)
        
        # get the bucket 次数最多的在后面
        ret = []
        
        for i in range(len(nums)-1, -1,-1):
            ret += bucket[i]
            if len(ret) >= k:
                break
                
        return ret[:k]

因为最多出现len(nums)次,所以最多就会有这么多个桶.

也有说有用堆排序的,就是维护一个大顶堆, 最后从堆里面弹出前面的k个就是的,就是也是建立好了字典之后,根据其出现的频率进行堆排序,不过感觉还是桶排序比较方便一些. 大致过程是,先建立个字典,然后建立一些桶,每个桶里面放的是出现这么多次数的那些数字, 最后从后往前把这些元素“加”起来即可,超过k个就停止. 桶的个数最多不会超过len(nums).

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦