LeetCode169. Majority Element C语言
|
1
2
|
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.
|
题意：找到数组中数量超过半数的.本题假设一定存在Majority Element。否则还得判断不存在怎么办。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
int
majorityElement(
int
* nums,
int
numsSize) {
//很明显第一种复杂度不行
// int size=0;
// if(numsSize%2==0){
// size=numsSize/2;
// }else{
// size=(numsSize-1)/2;
// }
// int i,j;
// int count=0;
// int flag=0;
// for(i=0;i<size;i++){
// count=1;
// // printf("%d---",flag);
// if(!flag){
// for(j=i+1;j<numsSize;j++){
// if(nums[j]==nums[i]){
// count++;
// }
// }
// // printf("%d",count);
// if(count>size){
// flag=i;
// break;
// }
// }else{
// break;
// }
// }
// return nums[i];
//网上一种专业算法Moore‘S voting Algorithem
//详情见http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html
//维护候选人和其出现的数量
int
candidate;
int
count=0;
for
(
int
i=0;i<numsSize;i++){
if
(count==0){
candidate=nums[i];
count++;
}
else
{
if
(nums[i]==candidate){
count++;
}
else
{
count--;
}
}
}
return
candidate;
}
|
PS:本来笨死的用了两层循环做出来。时间复杂度不过关。
然后网上找了一下，发现一个Moore's voting Algorithem 算法，专门解决这类问题的，还有算法演示。。。http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html
服！
本文转自 努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1867859