數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。
你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。
示例 1:

輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
輸出: 2
限制： 1 <= 數(shù)組長(zhǎng)度 <= 50000

來(lái)源：劍指Offer 面試題39
相關(guān)企業(yè)：

解法：摩爾投票
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)
思路：

• 票數(shù)和： 由于眾數(shù)出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半；若記眾數(shù)的票數(shù)為 +1 ，非眾數(shù)的票數(shù)為 ?1 ，則一定有所有數(shù)字的票數(shù)和 >0 。
• 票數(shù)正負(fù)抵消： 設(shè)數(shù)組 nums 中的眾數(shù)為 x ，數(shù)組長(zhǎng)度為 n 。若nums的前a個(gè)數(shù)字的票數(shù)和 =0 ，則數(shù)組后(n?a)個(gè)數(shù)字的票數(shù)和一定仍>0 （即后 (n?a) 個(gè)數(shù)字的 眾數(shù)仍為 x ）。

代碼：

def majorityElement(self, nums: List[int]) -> int:
        votes = 0
        for x in nums:
            if votes == 0: num = x
            votes += 1 if x == num else -1
        return num