Python AC O(n) bucket sort


  • 0
    A

    def topKFrequent(self, nums, k):

        freq, bucket, max_freq, res, count = collections.defaultdict(lambda:0, {}), collections.defaultdict(list), 0, [], k
        for n in nums:
            freq[n]+=1
            
        for ele in freq:
            bucket[freq[ele]].append(ele)
            max_freq = max(freq[ele], max_freq)
        
        for i in range(max_freq, -1, -1):
            if i in bucket:
                count-=len(bucket[i])
                n_ele = len(bucket[i]) - abs(count) if count < 0 else len(bucket[i])
                res+=bucket[i][:n_ele]
            if count <= 0:
                break
        
        return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.