Majority Element（多数元素）

题目 / Problem

中文： 给定一个大小为 n 的数组 nums，返回其中的多数元素。

多数元素是指在数组中出现次数严格大于 ⌊n / 2⌋ 的元素。可以假设数组中一定存在多数元素。

English: 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.

示例 / Examples

Example 1

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

3 出现了 2 次，而 ⌊3 / 2⌋ = 1，所以 3 是多数元素。
3 appears 2 times, and ⌊3 / 2⌋ = 1, so 3 is the majority element.

Example 2

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

2 出现了 4 次，而 ⌊7 / 2⌋ = 3，所以 2 是多数元素。
2 appears 4 times, and ⌊7 / 2⌋ = 3, so 2 is the majority element.

约束 / Constraints

• n == nums.length
• 1 <= n <= 5 × 10⁴
• -10⁹ <= nums[i] <= 10⁹
• 输入保证数组中一定存在多数元素。
  The input is generated such that a majority element always exists.

进阶 / Follow-up

能否在线性时间和 O(1) 额外空间内解决此问题？
Can you solve the problem in linear time and O(1) extra space?

解题思路：Boyer–Moore 投票算法 / Approach: Boyer–Moore Voting Algorithm

算法维护两个变量：
The algorithm maintains two variables:

• candidate：当前的多数元素候选值。
  candidate: the current majority-element candidate.
• count：候选值与其他值相互抵消后的剩余票数。
  count: the candidate's remaining vote count after cancellation with other values.

遍历数组中的每个元素 num：
For every element num in the array:

1. 如果 count === 0，将当前元素设为新的候选值。
   If count === 0, make the current element the new candidate.
2. 如果 num === candidate，将 count 加 1。
   If num === candidate, increment count.
3. 否则将 count 减 1，表示候选值与一个不同元素相互抵消。
   Otherwise, decrement count, representing cancellation between one candidate occurrence and one different element.

由于多数元素出现次数超过数组长度的一半，即使与所有其他元素两两抵消，最终仍会有剩余，因此最后的 candidate 一定是多数元素。
Because the majority element appears more than half the time, it remains after pairwise cancellation with every other element. Therefore, the final candidate must be the majority element.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {
  let candidate = 0;
  let count = 0;

  for (const num of nums) {
    if (count === 0) {
      candidate = num;
    }

    count += num === candidate ? 1 : -1;
  }

  return candidate;
}

题目保证多数元素存在，因此不需要再遍历一次验证候选值。
The problem guarantees that a majority element exists, so a second pass to verify the candidate is unnecessary.

执行过程 / Walkthrough

以 nums = [2,2,1,1,1,2,2] 为例：
For nums = [2,2,1,1,1,2,2]:

最终候选值为 2，因此返回 2。
The final candidate is 2, so return 2.

正确性直觉：两两抵消 / Correctness Intuition: Pairwise Cancellation

可以把一次 count-- 看作删除一对不同的元素。删除一对不同元素不会改变原数组中的多数元素：
Treat each count-- as removing a pair of different elements. Removing such a pair cannot change the majority element:

• 如果其中一个是多数元素，它和一个非多数元素同时被删除，多数元素的领先优势不变。
  If one is the majority element, it is removed together with a non-majority element, preserving its lead.
• 如果两个都不是多数元素，多数元素完全不受影响。
  If neither is the majority element, the majority element is unaffected.

不断执行这种抵消后，最终剩下的候选值就是多数元素。
After repeated cancellation, the surviving candidate is the majority element.

复杂度 / Complexity

• 时间复杂度：O(n)，数组只遍历一次。
  Time: O(n), because the array is traversed once.
• 空间复杂度：O(1)，只使用 candidate 和 count 两个额外变量。
  Space: O(1), because only the candidate and count variables are used.

哈希表解法 / Hash Map Approach

也可以统计每个元素的出现次数，一旦某个次数超过 ⌊n / 2⌋ 就返回该元素：
Another approach counts element frequencies and returns an element as soon as its count exceeds ⌊n / 2⌋:

function majorityElementWithMap(nums) {
  const counts = new Map();
  const threshold = Math.floor(nums.length / 2);

  for (const num of nums) {
    const count = (counts.get(num) ?? 0) + 1;
    counts.set(num, count);

    if (count > threshold) {
      return num;
    }
  }
}

• 时间复杂度 / Time: O(n)（假设哈希表操作平均为 O(1)）
  Assuming average O(1) hash-map operations.
• 空间复杂度 / Space: O(n)，最坏情况下需要记录大量不同元素。
  In the worst case, many distinct elements must be stored.

哈希表解法直观，但不满足进阶要求的 O(1) 空间。
The hash-map solution is intuitive but does not meet the O(1) extra-space follow-up.

排序解法 / Sorting Approach

数组排序后，多数元素一定占据中间位置：
After sorting, the majority element must occupy the middle position:

function majorityElementBySorting(nums) {
  nums.sort((a, b) => a - b);
  return nums[Math.floor(nums.length / 2)];
}

• 时间复杂度 / Time: O(n log n)
• 空间复杂度取决于排序实现，并且会修改原数组。
  Space usage depends on the sorting implementation, and the original array is modified.

如果不保证多数元素存在 / If a Majority Is Not Guaranteed

Boyer–Moore 算法仍会产生一个候选值，但该候选值不一定真正出现超过一半。此时必须再次遍历数组，验证它的出现次数是否大于 ⌊n / 2⌋。
Boyer–Moore still produces a candidate, but it may not actually occur more than half the time. In that case, a second pass is required to verify that its count exceeds ⌊n / 2⌋.

本题明确保证多数元素存在，所以可以直接返回候选值。
This problem explicitly guarantees a majority element, so the candidate can be returned directly.

易错点 / Common Pitfalls

• “多数元素”要求出现次数严格大于 ⌊n / 2⌋，不是大于或等于。
  A majority element appears strictly more than ⌊n / 2⌋ times, not greater than or equal to it.
• 当 count === 0 时，应先将当前元素设为候选值，再为它加一票。
  When count === 0, set the current element as the candidate before adding its vote.
• count 不是候选值在整个数组中的实际出现次数，而是抵消后的相对票数。
  count is not the candidate's actual total frequency; it is the relative count after cancellation.
• 排序解法需要数值比较函数 (a, b) => a - b，否则 JavaScript 默认按字符串排序。
  Numeric sorting in JavaScript requires (a, b) => a - b; otherwise values are sorted as strings.
• 只有在题目保证多数元素存在时，才能省略最终验证步骤。
  The final verification pass can be omitted only when the existence of a majority element is guaranteed.