[Solution] Simple python solution based on Voting


  • 5
    S

    The code is based on the elegant Majority Voting algorithm by Moore. (http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html)

    Runtime : O(N), Space: O(1)

    class Solution:
        # @param num, a list of integers
        # @return an integer
        def majorityElement(self, num):
            candidate = None
            count = 0
            for n in num:
                if candidate == None:
                    candidate = n
                    count += 1
                elif n == candidate:
                    count += 1
                elif n != candidate and count == 1:
                    candidate = None
                    count -= 1
                elif n != candidate:
                    count -= 1
            return candidate
    

  • 1
    H
    class Solution:
        # @param num, a list of integers
        # @return an integer
        def majorityElement(self, num):
            r = 1
            j = num[0]
            for i in num[1:]:
                if r==0:
                    j = i
                    r+=1
                elif i==j:
                    r=r+1
                else:
                    r=r-1
            return j
    

Log in to reply
 

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