Majority Number II

Question

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.

Find it.

Example Given [1, 2, 1, 2, 1, 3, 3], return 1.

Challenge O(n) time and O(1) extra space.

Thoughts

进阶1：思路是，如果出现3个不一样的数，就抵消掉。记录两个candidate和每个candidate分别的出现次数。如果遍历到的数和两个candidate都不等，就count都减1。最后可能会剩下两个candidate，再遍历一次整个数组验证一下谁是主元素。

面试官角度：

利用了抵消法的题目，还有“落单的数”（九章算法面试题1），同样是有进阶问题。对于进阶问题而言，关键是要理解“抵消”的思路，既然2个数可以抵消，那么3个数k个数也可以抵消。抵消之后，剩下来的数中，主元素一定仍然超过1/3, 1/k。对于1/k的情况（进阶2），其实在面试中一般来说不会问到，这个题的解法是源自一篇论文，所以不会做的同学也不必过于担心。但进阶1还是需要掌握的，因为进阶1说明是否真正理解了原问题的解法，还是只是背了答案。

Solution

class Solution:
    """
    @param nums: A list of integers
    @return: The majority number occurs more than 1/3
    """
    def majorityNumber(self, nums):
        # write your code here
        can1 = 0 
        can2 = 0
        count1 = 0
        count2 = 0
        for num in nums:
            if can1 == num:
                count1 += 1
            elif can2 == num:
                count2 += 1
            elif count1 == 0:
                can1 = num
                count1 += 1
            elif count2 == 0:
                can2 = num
                count2 += 1
            else:
                count1 -= 1
                count2 -= 1

        count1 = 0
        count2 = 0
        for num in nums:
            if can1 == num:
                count1 += 1
            elif can2 == num:
                count2 += 1
        return can1 if count1 > count2 else can2