Leetcode 169. Majority Element

https://leetcode.com/problems/majority-element/

The simple thought is using hash table to count. However, there is another tricky way. Because the number of majority is bigger than n/2, so if we add 1 when see it and subtract 1 when not see it, the final value should be larger than 0.

Solution:

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

Run Time: 72 ms