Leet: 347. Top K Frequent Elements-CodePudding

I have tried to solve the leetcode problem using list and dictionary. it passes for a few test cases but fails for some due to the range(k) passes as a parameter. Is there a way I could take care of all edge cases leetcode link:https://leetcode.com/problems/top-k-frequent-elements/

My soln:

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        d={}
        for each in range(len(nums)):
            if nums[each] not in d:
                d[nums[each]]=0
            d[nums[each]] =1
        res=[]
        if len(d)==k:
            return nums
        l=sorted(d.values(),reverse=True)
        for i in range(k):
            for k,v in d.items():
                if l[i]==v:
                    res.append(k)
        return res

CodePudding user response：

Others have given some solutions. I'd like to point out some of the problems in your code:

when len(d) == k, we need to return d.keys() instead of nums.

For example, when the nums = [1,1,1,1] and k = 1, we just need to return [1] instead of [1,1,1,1].

Try not to use variables with the same name.

We have a variable k in the input, and when iterating dict.items(), we don't want to create another variable named as k.

Think about a test case:

nums = [1,2,2,3,3]
k = 2

Your code will return [2,3,2,3] instead of [2,3]. Because l=[2,2,1] and elements appearing twice (2,3) will be added twice. One possible way to solve is adding d[k] = -1 after res.append(k).

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        d={}
        for each in range(len(nums)):
            if nums[each] not in d:
                d[nums[each]]=0
            d[nums[each]] =1
        res=[]
        if len(d)==k:
            return d.keys()
        l=sorted(d.values(),reverse=True)
        for i in range(k):
            for k,v in d.items():
                if l[i]==v:
                    res.append(k)
                    d[k] = -1
        return res

CodePudding user response：

the easiest solution to this would be to just count all items in the list and then, sort by count, like this

def topKfrequent(nums, k):
    d = dict()
    for n in nums:
        d[n] = d.setdefault(n, 0)   1
    sortedNumsKeys = sorted(d.keys(), key=lambda x: d[x], reverse=True)
    return sortedNumsKeys[:k]

CodePudding user response：

Another solution using collections.Counter:

from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return [i for i, _ in Counter(nums).most_common(k)]

CodePudding user response：

Soln:

class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    d={}
    for each in range(len(nums)):
        if nums[each] not in d:
            d[nums[each]]=0
        d[nums[each]] =1
    res=[]
    if len(d)==k:
        return d.keys()
    l=sorted(d.values(),reverse=True)
    for i in range(k):
        for key,v in d.items():
            if l[i]==v:
                res.append(key)
                d[key] = -1
    return res