Python, divide and conquer solution


  • 0
    G

    here is my solution:
    '''
    class Solution(object):
    def majorityElement(self, nums):
    if len(nums) == 1:
    return nums[0]

        if len(nums) == 2:
            if nums[0] == nums[1]:
                return nums[0]
            else:
                return None
        
        m1 = self.majorityElement(nums[0:len(nums)/2])
        m2 = self.majorityElement(nums[len(nums)/2:len(nums)])
        
        if m1 != None and self.count(nums, m1) > len(nums)/2:
            return m1
        if m2 != None and self.count(nums, m2) > len(nums)/2:
            return m2
    
    def count(self, nums, m):
        count = 0
        for i in nums:
            if i == m:
                count += 1
        return count
    

    '''


Log in to reply
 

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