题目：
排序后直接返回中间那个元素就行
1
2
3
4
5
6
7
8
9
10
11
12
| #include <algorithm>
#include <vector>
using std::vector;
class Solution {
public:
int majorityElement(vector<int> &nums) {
sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
};
|
一个简单事实：如果一个数组有大于一半的数相同，那么任意删去两个不同的数字，新数组还是会有相同的性质。基于这个事实，就引发了类似相消的思想：
由于众数一定占数组大小的一半以上，所以就算其它所有元素都来和它“碰”，到最后还是剩下众数，cur表示目前遍历到的候选众数，count表示目前为止该众数的“净”计数（对于待选众数，遇到相同的就++，遇到不同的就“碰撞”–，如果count变成0，就重新设置候选众数，count从1开始）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int majorityElement(vector<int>& nums) {
int i, n = nums.size();
int candidate = nums[0];
int cnt = 1;
for(i = 1 ; i < n; i++){
if(candidate == nums[i]){
cnt ++;
}else{
cnt --;
if(cnt == 0){
candidate = nums[i];
cnt = 1;
}
}
}
return candidate;
}
};
|
leetcode hot 100 rewrite, 从 0 开始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <vector>
using std::vector;
class Solution {
public:
int majorityElement(vector<int> &nums)
{
int i, n = nums.size();
int target = nums[0], cnt = 0;
for (i = 0; i < n; i++) {
if (nums[i] == target) {
cnt++;
} else {
cnt--;
if (cnt == 0 && i != n - 1)
target = nums[i + 1];
}
}
return target;
}
};
|
