Top K Frequent Elements

description

Accepted answer(third try):

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """

        dic = {}
        for i in nums:
            dic[i] = 0
        for i in nums:
            dic[i] += 1
        sorted_dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)
        output = []
        for i in range(k):
            output.append(sorted_dic[i][0])
        return output

A answer that suppostly have a better run time of O(n), but actually slower than my code

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        count = {}
        freq = [[] for i in range(len(nums) + 1)]

        for n in nums:
            count[n] = 1 + count.get(n, 0) #if no n in count, value set to 0, if there is n, + 1 to the old value
        for n, c in count.items():
            freq[c].append(n) # a list where the index is the number of occurence, and the sublist is the number who have that number of occurrence.
        output = []
        for i in range(len(freq) - 1, 0, -1): # going in decensing order from lenth-1 to 0
            for n in freq[i]:
                output.append(n)
                if len(output) == k:
                    return output

This is visual representation: