题解 | #数组中出现次数超过一半的数字#

NC73 数组中出现次数超过一半的数字

题意

给你一个数组，找出出现次数超过一半的数字。（也叫主元素问题）

1. 暴力法

枚举每一个数，看他是不是在数组中出现了超过一半的次数。

时间复杂度: $O(n^2)$ , 两重循环
空间复杂度: $O(1)$ .

2. 排序法

既然是众数且超过了一半，那么肯定也是中位数，排序后取中点即为所求。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n = numbers.size();
        sort(numbers.begin(), numbers.end());
        return numbers[n>>1];
    }
};

时间复杂度： $O(nlogn)$ . 依赖stl的sort方法。
空间复杂度： $O(1).$

3. 哈希表法

根据众数的定义，它出现的次数最多，所以用一个哈希表统计每个数字出现的次数，找最多的即可。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int, int> m;
        // 统计每个数字出现的次数
        for (auto v : numbers) m[v]++;

        // 找出现次数超过一半的
        for (auto [k, v] : m) {
            if (v > numbers.size()/2) return k;
        }
        // 兜底逻辑，没找到返回0
        return 0;
    }
};

时间复杂度： $O(n)$ . 遍历一轮数组和一轮map。
空间复杂度： $O(n)$ . 定义了一个大小为 $n$ 的map。

4. Boyer-Moore 投票算法（本题最佳算法）

这道题中，众数多了一个附加条件，出现的次数大于一半，那么说明该数比其他数字加起来出现的数都多。

Boyer-Moore 投票算法分为两步：

初始化两个变量，记录当前的候选值candidate和候选值出现的次数count。
第一轮遍历数组，如果count为0, 赋值当前元素予candidate，且count自加1；如果元素与candidate相等，count自加1，否则自减1。
第二轮遍历数组，若candidate在数组出现次数大于数组size一半，则为多数元素，否则不存在多数元素。

对于本题，题目有一个已知条件，说明超过一半的众数一定存在，故第二轮遍历可省略。

如图所示：
图片说明

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int res = 0, cnt = 0;
        for (auto v : numbers) {
            if (v == res) cnt++; // 遇到同样的数，票数+1
            else {
                cnt--; // 不同的数票数减一
                if (cnt <= 0) res = v, cnt = 1; // 没有数了，则当前的数为候选人, 注意不能写=0， 否则第一个数的边界上会wa
            }
        }

        // 第二轮遍历省略。

//         cnt = 0;
//         for (auto v : numbers) {
//             if (v == res) cnt++;
//         }
//         if (cnt < numbers.size()/2) return 0;
        return res;
    }
};

时间复杂度： $O(n)$ . 遍历一轮数组。
空间复杂度： $O(1)$ . 没有额外的数组定义