考研笔记

板子：主元素（摩尔投票）

主元素是出现次数 的元素。两个不同的元素互相抵消，主元素比其他所有元素加起来还多，抵消到最后剩下的一定是它。最后还要再扫一遍核实。

代码

int majority(int A[], int n) {             // 有主元素返回它，没有返回 -1
    int c = A[0], cnt = 1;                 // c：候选元素，cnt：候选的净票数；先让 A[0] 当候选
    for (int i = 1; i < n; i++) {
        if (A[i] == c) cnt++;              // 和候选相同，票数 +1
        else if (cnt > 0) cnt--;           // 不同，抵消一票
        else { c = A[i]; cnt = 1; }        // 票数已经是 0，换当前元素当候选（它自己算一票）
    }
    cnt = 0;                               // 第二趟：核实 c 是否真的过半
    for (int i = 0; i < n; i++)
        if (A[i] == c) cnt++;
    return cnt > n / 2 ? c : -1;           // 严格大于 n/2 才算过半
}

复杂度：时间 ，空间 。

备选解：计数数组

2013 年原题保证 ，可以直接计数：

int majorityCount(int A[], int n) {        // 时间 O(n)，空间 O(n)
    int *cnt = (int *)calloc(n, sizeof(int));
    int ans = -1;
    for (int i = 0; i < n; i++)
        if (++cnt[A[i]] > n / 2) { ans = A[i]; break; }
    free(cnt);
    return ans;
}

还有一种是先排序，主元素如果存在一定在正中间，再数一遍核实，时间 。

易错点

  • 第二趟核实不能省。投票只能保证「如果有主元素，那就是 c」；没有主元素时，c 可能是任意一个数。 例：(0,5,5,3,5,1,5,7) 投票后候选是 5，但 5 只出现了 4 次，没有超过 ，应该返回 。
  • 「过半」是严格大于 ，写成 cnt > n / 2。
  • 票数为 0 时，把当前元素设为候选、票数置 1，不是跳过当前元素。

链接

反向链接