如何用分治法求「多数元素」（出现次数超过一半的元素）？

简化版

多数元素指在数组里出现次数超过 ⌊n/2⌋ 的元素（题目保证一定存在）。分治：把数组分成左右两半，分别求各自的多数元素；若左右求出的候选相同，它就是答案；若不同，就在整个区间里数一下这两个候选各自出现多少次，取多的那个。递归式 T(n)=2T(n/2)+O(n) → O(n log n)。它的正确性靠一条引理：全局多数元素，必然也是左半或右半至少一边的多数元素。

详细版

关键引理：如果元素 e 是整个数组的多数元素，那它至少是左半或右半其中一半的多数元素。

反证：若 e 在左右两半都不过半，则它在左半出现 ≤ 左半长度/2、在右半 ≤ 右半长度/2，加起来 ≤ n/2，与「e 出现 > n/2」矛盾。

所以全局答案一定藏在 {左半多数, 右半多数} 这两个候选里，只需验证它们。

int majorityElement(int[] a) {
    return divide(a, 0, a.length - 1);
}
int divide(int[] a, int lo, int hi) {
    if (lo == hi) return a[lo];                 // 递归基：单元素就是它自己的多数
    int mid = lo + (hi - lo) / 2;
    int left  = divide(a, lo, mid);
    int right = divide(a, mid + 1, hi);
    if (left == right) return left;             // 两半答案一致，直接就是它
    int lc = count(a, lo, hi, left);            // 否则在整段里数两个候选
    int rc = count(a, lo, hi, right);
    return lc > rc ? left : right;
}
int count(int[] a, int lo, int hi, int val) {
    int c = 0;
    for (int i = lo; i <= hi; i++) if (a[i] == val) c++;
    return c;
}

时间 O(n log n)、空间 O(log n)（递归栈）。
实际最优是摩尔投票，O(n) 时间、O(1) 空间；分治版主要用于演示「合并」。

完整版教学

一、问题定义与常见解法

多数元素：在长度为 n 的数组里出现次数严格超过 ⌊n/2⌋ 的元素（LeetCode 169，通常保证一定存在）。因为它占了一半以上，具备很多好性质。常见解法有：

哈希计数：统计每个数出现次数，取最大——O(n) 时间、O(n) 空间。
排序取中位数：排序后下标 n/2 处一定是多数元素——O(n log n)。
分治：本题重点，O(n log n)，用来练「合并」。
摩尔投票：最优，O(n) 时间、O(1) 空间。

二、分治的关键引理：全局多数必是某一半的多数

分治要成立，得先想清楚：把数组切成左右两半后，全局的多数元素跑哪去了？

引理：若 e 是整个数组的多数元素，则它至少是左半或右半之一的多数元素。

用反证法：假设 e 在左半、右半都没过半。那么它在左半的出现次数 ≤ ⌊左半长度/2⌋，在右半 ≤ ⌊右半长度/2⌋，两者相加 ≤ n/2。但 e 作为全局多数出现次数 > n/2，矛盾。所以它至少在一半里过半。

这条引理保证了：全局答案一定出现在「左半的多数元素」或「右半的多数元素」之中——我们只要递归求出两半各自的候选，答案必是这两个之一，不会漏。

三、合并：候选相同直接取，不同就数一数

有了引理，合并步就清楚了：

递归求出左半多数 left、右半多数 right；
若 left == right：两半指向同一个元素，它显然就是整段的多数，直接返回；
若 left != right：答案必是二者之一（引理保证），于是在当前整段区间里数 left 和 right 各出现几次，谁多谁是这段的多数，返回它。

递归基是单个元素——一个元素显然是它自己那个长度为 1 的数组的多数元素。

四、复杂度 O(n log n)

每层分成两个半规模子问题：2T(n/2)；
合并时最多数两遍整段：O(n)；
合起来 T(n)=2T(n/2)+O(n) → O(n log n)，空间 O(log n)（递归栈）。

比哈希法（O(n) 但费空间）和排序法（同为 O(n log n)）没有优势，它的价值在于清晰演示分治如何用「候选 + 验证」来合并。

五、和摩尔投票 O(n)/O(1) 对比

这题的最优解是摩尔投票（Boyer–Moore Voting）：

int majorityElement(int[] a) {
    int cand = a[0], votes = 0;
    for (int x : a) {
        if (votes == 0) cand = x;          // 票数归零，换候选
        votes += (x == cand) ? 1 : -1;      // 同则 +1，异则 -1
    }
    return cand;                             // 保证存在时即为多数元素
}

直觉：把「多数元素」和「其他元素」两两抵消，因为多数元素占了一半以上，抵消到最后剩下的一定是它。一次遍历、O(n) 时间、O(1) 空间，全面优于分治。

面试取舍：只求「多数元素（>n/2）」用摩尔投票最优；但分治的「递归求候选、合并时验证」是一种通用套路，遇到「不保证存在」或变体（如求出现超过 n/3 的元素）时，这种思路更易改造。

六、递归式、合并证明与数字推演

这道题的分治闭环是：若某元素在整体中超过 n/2 次，它至少在左半或右半中成为该半的多数候选。递归调用只保证子问题正确，原问题能否正确仍取决于合并步骤是否覆盖所有情况且不重不漏。

T(n)=2T(n/2)+Θ(n)=Θ(n log n)
递归树核对：每层子问题数 × 单个子问题的非递归代价

带数字推演：[2,2,1,1,1,2,2] 左右候选不同，合并层在完整区间计数后选择 2。推演时应记录每层输入规模、进入哪些子问题、合并新增了什么信息，不能只写最终答案。

记忆钩子：先写“分成什么、递归返回什么、怎样合并”，再列递推式；只会套主定理而说不清合并，说明算法还没有真正掌握。

七、实现代价、退化条件与替代方案

实现边界是：题目若不保证多数存在，最终必须验证候选次数；实际面试通常更优先摩尔投票。除了渐进时间，还要把递归栈、辅助数组、输入是否被修改以及最坏输入考虑进去。

检查项	面试中要回答的内容
基本情况	规模 0 或 1 时如何直接返回
规模缩小	每次递归是否严格靠近基本情况
合并正确性	子解怎样推出原问题答案
资源代价	递归深度、辅助结构与数据复制
退化保护	随机化、阈值切换、预排序或迭代改写

测试至少覆盖最小规模、奇偶长度、全部相等、严格有序/逆序、极端偏斜划分和会触发最大计数或溢出的数据。若存在更直接的线性算法、堆算法或动态规划，还要说明分治方案的教学价值与工程取舍。

八、常见误区与追问

误区：左右候选不同就随便选一个。 必须在当前区间重新计数比较。
误区：全局多数必同时是两半多数。 只保证至少是某一半的多数候选。
误区：分治是最优解。 摩尔投票可做到 O(n) 时间、O(1) 空间。
追问：关键引理如何证明？ 若它在两半都不超过各自一半，总次数就不可能超过整体一半。
追问：为什么合并导致 n log n？ 每层所有区间计数总量 n，共 log n 层。
追问：无保证版本怎么返回？ 先产生候选，再全数组计数确认是否超过 n/2。

九、加强记忆

多数元素（出现 > ⌊n/2⌋）的分治：切两半、各求候选，两半候选相同则直接是答案，不同则在整段数两个候选的出现次数取多者。正确性靠引理——全局多数必是某一半的多数（否则两半都不过半，总数 ≤ n/2 矛盾）。T(n)=2T(n/2)+O(n) → O(n log n)。最优解是摩尔投票（异号抵消、O(n)/O(1)），分治胜在演示「候选 + 验证」的合并套路。

简化版

详细版