一、题目描述
力扣链接：力扣169.多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
二、C++题解
2.1 暴力解法
直接遍历两遍数组，记录每个元素出现的次数，一旦有元素出现的次数超过n/2，直接返回该元素。缺点是时间复杂度来到了O(n^2)，对于某些案例超时。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
int count = 0;
for (int j = 0; j < n; ++j) {
if (nums[i] == nums[j]) {
++count;
}
}
if (count > n/2) {
return nums[i];
}
}
return -1;
}
};
2.2 摩尔投票法
该算法的基本思想是通过维护一个候选元素和一个计数器，来消除数组中不同元素之间的相互抵消。如果存在多数元素，最终候选元素就是所求的多数元素。
设输入数组 nums 的众数为 x ，数组长度为 n 。
推论一： 若记 众数 的票数为 +1，非众数 的票数为 −1 ，则一定有所有数字的票数和 >0 。
推论二： 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n−a)个数字的 票数和一定仍 >0，即后 (n−a)个数字的众数仍为 x。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int x = 0, votes = 0;
for (int num : nums){
if (votes == 0) x = num;
votes += num == x ? 1 : -1;
}
return x;
}
};
2.3 哈希表
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> countMap;
// 先生成哈希表
for (auto num : nums) {
++countMap[num];
}
// 找到出现次数最多的
int target = 0, count = 0;
for (auto& entry : countMap) {
if (entry.second > count) {
target = entry.first;
count = entry.second;
}
}
return target;
}
};
