One-pass solution with only 2 variables' extra space

  • 6

    using this property: when removing 2 distinct elements from array, the majority element will still be the same.

    class Solution(object):
    def majorityElement(self, nums):
        :type nums: List[int]
        :rtype: int
        a,c = None, 0 # a is current majority number, c is the count 
        for n in nums:
            if c==0: a,c = n, 1
            elif a==n: c += 1
            else: c -= 1
        return a

Log in to reply

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