Python solution with detailed explanation


  • 0
    G

    Solution

    Boyer Moore

    class Solution(object):
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            counter, candidate = 0, None
            for c in nums:
                if counter == 0:
                    counter,candidate = 1, c
                elif c == candidate:
                    counter = counter + 1
                else:
                    counter = counter - 1
            return candidate
    

    There are several other algorithms. These are explained here: https://discuss.leetcode.com/topic/17446/6-suggested-solutions-in-c-with-explanations

    HashTable Solution

    • Do an early exit if a solution is found
    class Solution(object):
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            counter, N, result = {}, len(nums), None
            for c in nums:
                if c in counter:
                    counter[c] = counter[c] + 1
                else:
                    counter[c] = 1
                if counter[c] > N//2:
                    result = c
                    break
            return result
    

    Sorting Based Solution

    • Just sort the array and return N//2 element.
    class Solution(object):
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            nums.sort()
            return nums[len(nums)//2]
    

    Randomized Algorithm

    • Best case O(N) and worst case O(N^2)
    from random import randint
    class Solution(object):
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            while True:
                count,idx = 0, randint(0, len(nums)-1)
                for c in nums:
                    if c == nums[idx]:
                        count = count + 1
                if count >= len(nums)//2 + 1:
                    return nums[idx]
            return
    

    Divide and Conquer

    • The majority element is either the majority in left or right side. Recursively find the solution for left and right and test it out.
    class Solution(object):
        def majorityElement_divide_conquer(self, nums, low, high):
            """
            :type nums: List[int]
            :rtype: int
            """
            if low == high:
                return nums[low]
            mid = low + int((high-low)/2)
            lm = self.majorityElement_divide_conquer(nums, low, mid)
            rm = self.majorityElement_divide_conquer(nums, mid+1, high)
            if lm == rm:
                return lm
            lcount,rcount = nums[low:high+1].count(lm), nums[low:high+1].count(rm)
            return lm if lcount > rcount else rm
        
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return self.majorityElement_divide_conquer(nums, 0, len(nums)-1)
    

Log in to reply
 

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