简介
- 给出n个元素的数组，希望找出其中数量超过 n/2 的元素。注意是>,不是>=。
- 题目保证一定有多数元素,但是这里给出了没找到多数元素的情况。
- 时间复杂度O（n）
法一：遍历计数
- 对每个出现的元素都遍历一遍，求出其次数。
- 或者通过链表，在节点里面加上元素出现次数这个信息，寻找节点里面count最大的元素。
法二：排序取中
- 相对于暴力的遍历，排序取中算法是在排序好的数组中取中间元素，这个元素一定是多数元素。
- 但是有时候对数组进行排序也很麻烦。
法三：剔除元素
前情提要：在原序列剔除两个不同的元素，多数元素不变，还是原来那个。简单证明如下：
- 假设多数元素个数为c，其他元素个数n-c；
- 若剔除一个多数元素，一个其他元素，原来就满足c>n/2,与现在满足多数元素的条件 c-1>(n-2)/2 完全等价
- 若剔除两个不同的其他元素，多数元素在新数组里面的数量优势还被放大了，更加满足多数元素的条件。
代码编写细节
删除这个操作在内存上是不好做的，我们用count这个变量来模拟删除操作。count是当前候选元素和其他元素的个数相减,也就是净个数。当等于0，就可以把前面的元素都舍弃。
// 递归，寻找多数元素的候选者
int candidate(int a[],int n,int start) {if(start>=n)return -9999;int i=start; int c=a[start]; // 候选元素cint count =1;while(i<n-1 && count>0){ // 目前候选元素个数比较多（count>0），并且还没比较完所有的元素，继续循环。i++;if(a[i]==c) count++;else count--;}if(i==n-1) return c;else return candidate(a,n,i+1);
}
这个函数返回c或者-9999；但是实际上只要i遍历到了最后一个元素，即是他不是多数元素，他也会被返回。
所以我们再次验证：
int main(){int n;cin>>n;int a[n];for(int i=0;i<n;i++) cin>>a[i];int c=candidate(a,n,0);if(c==-9999) cout<<"没有多数元素";else{int count=0;for(int i=0;i<n;i++)if(a[i]==c) count++;if(count > (n/2) ) cout<<c;else cout<<"没有多数元素";}return 0;
}
以上两段拼起来就是完整代码，如下：
点击查看代码
#include<iostream>
using namespace std;
int candidate(int a[],int n,int start) {if(start>=n)return -9999;int i=start; int c=a[start]; // 候选元素cint count =1;while(i<n-1 && count>0){ // 目前候选元素个数比较多（count>0），并且还没比较完所有的元素，继续循环。i++;if(a[i]==c) count++;else count--;}if(i==n-1) return c;else return candidate(a,n,i+1);
}
int main(){int n;cin>>n;int a[n];for(int i=0;i<n;i++) cin>>a[i];int c=candidate(a,n,0);if(c==-9999) cout<<"没有多数元素";else{int count=0;for(int i=0;i<n;i++)if(a[i]==c) count++;if(count > (n/2) ) cout<<c;else cout<<"没有多数元素";}return 0;
}
附：确保数组一定有多数元素的版本：
点击查看代码
#include<iostream>
using namespace std;
int candidate(int a[],int n,int start) {int i=start; int c=a[start]; // 候选元素cint count =1;while(i<n-1 && count>0){ i++;if(a[i]==c) count++;else count--;}if(i==n-1 || count>0 ) return c;else return candidate(a,n,i+1);
}
int main(){int n;cin>>n;int a[n];for(int i=0;i<n;i++) cin>>a[i];int c=candidate(a,n,0);cout<<c;return 0;
}