Python solution generalized to find n/k majority


  • -3
    L
    class Solution(object):
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            return self.findKMajority(nums, 3)
        
        def findKMajority(self, nums, k):
            if (k<1): return []
            if (k==1):
                if (nums.count(nums[0])==len(nums)):
                    return [nums[0]]
                else:
                    return []
    
            dic={i:0 for i in xrange(k-1)}
            for x in nums:
                if x in dic:
                    dic[x] += 1
                else:
                    updated=False
                    for key in dic:
                        if (dic[key]==0):
                            dic.pop(key)
                            dic[x]=1
                            updated=True
                            break
                        
                    if (not updated):
                        for key in dic:
                            dic[key] -=1
            return filter(lambda x: nums.count(x)>len(nums)/k, dic.keys())

Log in to reply
 

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