169. 多数元素

这是一个经典问题，可以使用多种方法解决。考虑到效率，我将使用摩尔投票算法（Boyer-Moore Voting Algorithm），它只需要 O(n) 时间复杂度和 O(1) 空间复杂度。

public class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        // 摩尔投票算法
        for (int num : nums) {
            // 当计数器为0时，选择当前元素作为新的候选者
            if (count == 0) {
                candidate = num;
            }

            // 如果当前元素等于候选者，计数器+1，否则-1
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

算法解析：

1. 摩尔投票算法原理：

   • 初始化一个候选元素 candidate 和计数器 count = 0
   • 遍历数组中的每个元素：
     • 当 count 为 0 时，将当前元素设为新的候选者
     • 如果当前元素等于候选者，count 加 1
     • 否则，count 减 1
   • 由于多数元素出现次数超过 n/2，最终剩余的候选者必然是多数元素

2. 为什么有效：

   • 每次遇到不同元素时，它们会互相抵消
   • 由于多数元素数量超过一半，其他所有元素加起来也无法完全抵消它
   • 最终剩下的候选元素一定是多数元素

3. 复杂度分析：

   • 时间复杂度：O(n)，只需遍历数组一次
   • 空间复杂度：O(1)，只使用了常数级额外空间

4. 优势：

   • 比哈希表计数法更节省空间
   • 比排序法更高效（排序需要 O(n log n) 时间）
   • 适用于流式数据，不需要一次性加载所有数据