My python solution,one is hash table and th other one is Moore voting algorithm


  • 0
    W

    This is the hash table solution, coat 132ms, O(n)

    class Solution:
        # @param num, a list of integers
        # @return an integer
        def majorityElement(self, num):
            hashed = {}
            most = len(num) // 2
            for index, value in enumerate(num):
                if value in hashed:
                    hashed[value] += 1
                else:
                    hashed[value] = 1
                if hashed[value] > most:
                    return value
    

    And this is the Moore voting algorithm, cost 133ms, O(n)

    class Solution:
        # @param num, a list of integers
        # @return an integer
        def majorityElement(self, num):
            counter = 0
            candidate = num[0]
            for i in xrange(len(num)):
                if num[i] == candidate:
                    counter += 1
                else:
                    counter -= 1
                    if counter == 0:
                        candidate = num[i]
                        counter = 1
            return candidate

Log in to reply
 

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