vvrf / DSA.log

问题拆解

多数元素是出现次数 严格大于 ⌊n/2⌋ 的元素，题目保证它一定存在。

最直接的想法是用哈希表统计每个元素出现多少次，再挑出次数过半的那个。这样思路清晰，但要额外花 O(n) 的空间。进阶要求把空间压到 O(1)，就得利用“过半”这个很强的条件，而不只是数数。

多数元素比其他所有元素加起来还多，如果让不同的元素两两抵消，最后剩下的必然是它。

哈希计数（作为对照）

public int majorityElement(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums) {
        int c = count.merge(x, 1, Integer::sum);
        if (c > nums.length / 2) {
            return x;
        }
    }
    return -1; // 题目保证多数元素存在，走不到这里
}

def majorityElement(nums):
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
        if count[x] > len(nums) // 2:
            return x

func majorityElement(nums []int) int {
    count := make(map[int]int)
    for _, x := range nums {
        count[x]++
        if count[x] > len(nums)/2 {
            return x
        }
    }
    return -1 // 题目保证多数元素存在，走不到这里
}

pub fn majority_element(nums: Vec<i32>) -> i32 {
    let mut count = std::collections::HashMap::new();
    for &x in &nums {
        let c = count.entry(x).or_insert(0);
        *c += 1;
        if *c > nums.len() / 2 {
            return x;
        }
    }
    unreachable!() // 题目保证多数元素存在
}

这版本一眼就对，适合先确认题意。它的问题只在空间：最坏情况下要为几乎所有不同元素各记一笔。

摩尔投票

维护一个候选人 candidate 和一张票数 count。遍历时，票数为 0 就把当前元素立为新候选人；之后遇到相同元素票数加一，遇到不同元素票数减一——相当于一张反对票抵消一张支持票。

public int majorityElement(int[] nums) {
    int count = 0;
    int candidate = 0;
    for (int x : nums) {
        if (count == 0) {
            candidate = x;
        }
        count += x == candidate ? 1 : -1;
    }
    return candidate;
}

def majorityElement(nums):
    count = 0
    candidate = None
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

func majorityElement(nums []int) int {
    count, candidate := 0, 0
    for _, x := range nums {
        if count == 0 {
            candidate = x
        }
        if x == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}

pub fn majority_element(nums: Vec<i32>) -> i32 {
    let mut count = 0;
    let mut candidate = 0;
    for x in nums {
        if count == 0 {
            candidate = x;
        }
        count += if x == candidate { 1 } else { -1 };
    }
    candidate
}

为什么最后剩下的一定是多数元素？把每个非多数元素看成消耗掉一张多数元素的票。多数元素的票数超过一半，其余所有元素加起来也不够把它的票全部抵消，所以无论顺序如何打乱，它的净票数始终为正，最终稳稳占据 candidate。

因为题目保证多数元素存在，这里不需要第二遍验证；如果不保证，还得再扫一遍确认候选人真的过半。

复杂度

指标	复杂度	原因
时间	`O(n)`	一次遍历完成抵消
空间	`O(1)`	只保存候选人和票数

可以迁移的模式

存在一个“数量占绝对优势”的元素；
允许用抵消、配对来消去噪声，而不是精确计数；
目标是把空间从 O(n) 压到常数。

摩尔投票还能推广到“出现次数超过 ⌊n/3⌋”，那时维护两个候选人即可。