超过数组元素一半C++

多数元素问题的解决方案
对于寻找数组中出现次数超过一半的元素（即多数元素），有多种方法可以实现这一目标。以下是几种常见的解决策略：
使用哈希表统计频率
一种直观的方法是利用哈希表来记录每个元素出现的频次，并找出那个出现次数最多的元素作为返回结果。
class Solution {
public:
int majorityElement(std::vector<int>& nums) {
std::unordered_map<int, int> counts;
int majority = 0, cnt = 0;

for (int num : nums) {
++counts[num];
if (counts[num] > cnt) {
majority = num;
cnt = counts[num];
}
}

return majority;
}
};

这种方法通过遍历整个列表并更新计数值，最终找到最大值对应的键就是所求的结果[^1]。
排序取中间位置
另一种简单有效的方式是对输入数据先进行排序操作，之后直接选取位于序列中央的那个元素即可得到答案。这是因为当某个特定值占据了超过总数的一半时，在有序排列下它必然会处于中心的位置上。
class Solution {
public:
int majorityElement(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
};

此方案基于排序后的特性快速定位到众数所在之处[^2]。
Boyer-Moore 投票算法
还有一种更为高效的线性时间复杂度 O(n) 的算法——Boyer-Moore 投票算法。该算法的核心思想是在一轮扫描过程中动态维护候选者及其支持数量；每当遇到不同的项就减少当前候选人得票直至清零，则更换新的候选人继续累加直到结束为止。
class Solution {
public:
int majorityElement(std::vector<int>& nums) {
size_t length = nums.size();
int candidate = nums[0], count = 1;

for (size_t i = 1; i < length; ++i) {
if (candidate != nums[i])
--count;
else
++count;

if (!count && i + 1 < length) {
candidate = nums[++i];
count = 1;
}
}

return candidate;
}
};

这段代码实现了上述逻辑，能够在线性时间内完成任务而不需额外空间开销[^3][^4]。
针对更复杂的场景比如要找多个频繁出现的项目或者比例低于一半但仍占较大比重的情况，还可以考虑扩展版本如摩尔投票法的应用[^5]。