数组中出现次数超过一半的数字
通过比例：21.01%最佳记录：0 ms|0K（来自shi_kai）
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
如果允许时间复杂度是O(nlogn)的话，自然会想到快排；排个序，然后再取就可以了。
//当然这里给一秒那也是肯定可以的；
#include<algorithm>class Solution {public:int MoreThanHalfNum_Solution(vector<int> numbers) {if(numbers.size()==0) return NULL;if(numbers.size()==1) return numbers[0];sort(numbers.begin(),numbers.end());int num,cnt;bool bo=false;for(int i=0;i<numbers.size()/2;i++){num=numbers[i];cnt=1;for(int j=i+1;j<numbers.size();j++){if(num==numbers[j]) cnt++;if(cnt>numbers.size()/2) {bo=true;break;}}if(bo) break;}if(!bo) return 0;else return num;}};
//当然这肯定不是面试官期望得到的答案。如果你O（n）呢？
我们可以利用快排的原理来解决，因为超过一半的数，那么快排的时候，如果哨兵在中位数，那么它一定是我们要求的数，然后这样还没完，eg：2 3 4 1 2 中位数是2但是出现次数没超一半，所以要最后判断！
class Solution {public:int MoreThanHalfNum_Solution(vector<int> numbers) {int len=numbers.size();if(len==0||len==1) return NULL;int k=Qsort(numbers,0,len-1,len/2);//检查次数是否过半;int cnt=0;for(int i=0;i<len;i++){if(cnt>len/2) break;if(numbers[i]==k) cnt++;}if(cnt<=len/2) k=0;return k;}int Qsort(vector<int> num,int low,int high,int ans){//for(int i=low;i<=high;i++)//{//printf("%d ",num[i]);//}//printf("\n");if(low<high){int po=Partition(num,low,high);if(po==ans) return num[po];if(po<ans) return Qsort(num,po+1,high,ans);else if(po>ans) return Qsort(num,low,po-1,ans);}return num[low];}int Partition(vector<int> &num,int low,int high){int tmp=num[low];while(low<high){while(low<high && num[high]>=tmp)high–;num[low]=num[high];while(low<high && num[low]<=tmp) low++;num[high]=num[low];}num[low]=tmp;//printf("%d\n",low);return low;}};
//那么如果面试官不让修改原数组呢？那我们就只能利用数组的规律了，出现一半以上的数的个数一定超过所有数，所以送第一个数开始往后，记录数字和次数；相同次数加一，不同次数减一，当次数为0的时候赋上新值，继续往后，，，，，，当然最后也是要判断出现次数的，eg：1 2 3 2 4 2 5
/***首先要知道超过一半，意味着len/2的位置就是你要求的数了，其次要求时间复杂度为O(n),那么可以利用快排的原理哦！*/#include<stdio.h>#include<vector>using namespace std;/**不允许修改数组的前提下*/class Solution {public:int MoreThanHalfNum_Solution(vector<int> numbers) {int len=numbers.size();if(len==0) return NULL;int cnt=1,num=numbers[0];for(int i=1;i<len;i++){if(num==numbers[i]) cnt++;else if(cnt>0&&num!=numbers[i]) cnt–;if(cnt==0) {num=numbers[i];cnt=1;}}if(cnt<=0) return NULL;int c=0;for(int i=0;i<len;i++){if(num==numbers[i]) c++;if(c>len/2) break;}if(c<=len/2) return 0;return num;}};int main(){vector<int> arr;int n;while(scanf("%d",&n)!=EOF){int tmp;arr.clear();for(int i=0;i<n;i++){scanf("%d",&tmp);arr.push_back(tmp);}Solution so;printf("%d\n",so.MoreThanHalfNum_Solution(arr));}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
学习不是人生的全部，但学习都征服不了，那我还能做什么?
