Simple O(n) time O(1) space complete solution


  • 1
    N

    The observation is that a majority element in the whole list has to be a local majority element in some sublist.

    On the other hand, it is possible that a local majority element does not necessarily be the majority element in the whole list, as some list may not have a majority element, e.g., 1, 1, 1, 2, 2, 3, 3, 3. Thus we need to validate the candidate in the end to make sure it is indeed a majority element of the whole list.

    class Solution(object):
        def getCandidate(self, nums):
            count = 0
            for num in nums:
                if count is 0:
                    candidate = num
                if candidate == num:
                    count += 1
                else:
                    count -= 1
            return candidate
            
        def validateCandidate(self, nums, candidate):
            count = 0
            for num in nums:
                if num == candidate:
                    count += 1
            return candidate if count > len(nums) / 2 else -1
        
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            candidate = self.getCandidate(nums)
            return self.validateCandidate(nums, candidate)
    

Log in to reply
 

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