Majority Number

Question

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

otherwise the algo doesn't work. like [1,2,3,4,5,6,7]

Thoughts

如果没有extra space O(1)的限制的话，其实很简单 用一个hashtable去记录次数，最后求出出现次数大于一半的即可

jiuzhang

采用抵消法。一旦发现数组中存在两个不同的数，就都删除，直到剩下的数都一样。此时剩下的数就是主元素。因为每次抵消操作之后，剩下来的数种，主元素一定也还是超过一半的。具体实现的时候，记录一个candidate和其出现的次数count，遍历每个数，如果count==0，则把candidate置为遍历到的数，否则看遍历到的数和candidate是否相等，如果相等，则count++，否则count--（抵消），遍历结束后，candidate就是主元素。

这个方法在assume存在majority number的时候是成立的，如果没有这个前提，则要再loop一次找到这个数出现的次数是否确实大于一半

Solution

class Solution:
    """
    @param nums: A list of integers
    @return: The majority number
    """
    def majorityNumber(self, nums):
        # write your code here
        candidate = 0
        count = 0
        for num in nums:
            if count == 0:
                candidate = num
                count += 1
            elif num == candidate:
                count += 1
            else:
                count -= 1
        return candidate