描述
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
分析
貌似是某本算法书上的例题（以后遇到了再加上）。题目中描述，这个数一定是存在的，那么可以像玩连连看一样，不过将不同的元素看做一对，遇到这样一对就删除，留下的一定是超过⌊ n/2 ⌋的
解决方案1(C++)
暴力的方式是这样的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int majorityElement(vector<int>& nums) {
map<int, int> map_int_int;
for(int i = 0; i < nums.size(); ++i) {
map<int, int>::iterator int_iter = map_int_int.find(nums[i]);
if(int_iter == map_int_int.end()){
map_int_int[nums[i]] = 1;
}else {
map_int_int[nums[i]]++;
}
if(map_int_int[nums[i]] > nums.size()/2) {
return nums[i];
}
}
return 0;
}
};
|
某本书上的算法思想：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int majorityElement(vector<int>& nums) {
int result;
int count = 0;
for(int i = 0; i < nums.size(); i++) {
if(count == 0) {
result = nums[i];
count = 1;
}else {
if(result == nums[i]) {
count++;
}else {
count--;
}
}
}
return result;
}
};
|
在讨论里发现一种很有意思的方法：TODO：写出数学分析(一尺之捶，日取其半，万世不竭，所以，极限是？)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int majorityElement(vector<int> &num) {
int count = 0;
while(true) {
if(num.size() == 1) {
return num[0];
}else {
int i = rand() % (num.size() - 1);
for(int j = 0; (unsigned)j < num.size(); j++) {
if(num[j] == num[i]){
count++;
}
}
if((unsigned)count > (num.size()/2)) {
return num[i];
}else {
count = 0;
continue;
}
}
}
}
};
|
解决方案2（Golang）
1
2
3
4
| func majorityElement(nums []int) int {
sort.Ints(nums)
return nums[len(nums)/2]
}
|
相关问题