Problem: 169. 多数元素
解析
hash表
hash表法，遍历数组，记录每个元素出现的次数，最后返回出现次数大于n/2的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
int majorityElement(vector<int> &nums) {
unordered_map<int, int> hashTable;
for (int i = 0; i < nums.size(); ++i) {
if (hashTable.find(nums[i]) != hashTable.end()) {
++hashTable[nums[i]];
} else {
hashTable.insert({nums[i], 1});
}
}
for (auto e : hashTable) {
if (e.second > nums.size() / 2) {
return e.first;
}
}
return 0;
}
};
|
排序
排序法，排序后，中间元素一定是出现次数大于n/2的元素。
用反证法证明：如果中间元素不是出现次数大于n/2的元素，那么出现次数大于n/2的元素一定在中间元素的左边或右边，那么左边或右边的元素个数大于n/2，与中间元素不是出现次数大于n/2的元素矛盾。
1
2
3
4
5
6
7
8
|
class Solution {
public:
int majorityElement(vector<int> &nums) {
sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
};
|
投票法
遍历数组，记录当前元素和次数，如果次数为0，更新当前元素，次数为1，否则次数加一或减一。最后是多数派的胜利
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int majorityElement(vector<int> &nums) {
int winner = nums[0], cnt = 1;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] != winner) {
--cnt;
if (cnt < 0) {
winner = nums[i];
cnt = 1;
}
} else {
++cnt;
}
}
return winner;
}
};
|
