169. Majority Element

math

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

• n == nums.length

• 1 <= n <= 5 * 104

• -109 <= nums[i] <= 109

Follow-up: Could you solve the problem in linear time and in O(1) space?

分析：

Boyer-Moore算法原理

直觉上： 如果一个元素超过一半，那么"抵消掉"其他元素，它还会剩下来。

步骤：

1. 一开始没有候选人（candidate），票数是0。

2. 遍历数组：

   • 如果票数是0，选当前元素作为新的候选人。

   • 如果当前元素==候选人，票数+1。

   • 如果当前元素≠候选人，票数-1。

3. 遍历完后，手上拿着的candidate，可能就是多数元素。

4. 最后验证一下，真的出现了超过n/2次吗？如果是，返回candidate；否则返回-1。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate