Majority Number

题目描述

解题方法

关键是消去法的思想。

Solution

class Solution:
    # @param A : tuple of integers
    # @return an integer
    def repeatedNumber(self, A):
        if not A:
            return -1

        can1 = 0
        can2 = 0
        count1 = 0
        count2 = 0
        for num in A:
            if num == can1:
                count1 += 1
            elif num == can2:
                count2 += 1
            elif count1 == 0:
                can1 = num
                count1 += 1
            elif count2 == 0:
                can2 = num
                count2 += 1
            else:
                count1 -= 1
                count2 -= 1

        num1 = 0
        num2 = 0
        for num in A:
            if num == can1:
                num1 += 1
            elif num == can2:
                num2 += 1
        if num1 > len(A) / 3:
            return can1
        elif num2 > len(A) / 3:
            return can2
        return -1

Reference