题目描述：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
#思路
因为元素出现的次数超过了一半，所以很明显，可以先排序，然后数组的中间的元素就是要找的出现超过一半的元素，然后进行检验，如果没有一半，则输出0。
#code
int MoreThanHalfNum_Solution(vector<int> numbers) {if(numbers.size()==0)return 0;sort(numbers.begin(),numbers.end());int num=numbers[numbers.size()/2];int count=0;for(int i=0;i<numbers.size();i++){if(num==numbers[i])count++;}if(count>=(numbers.size()/2+1))return num;return 0;}
#思路
已经说过了，上面那个是ologn的，可以将复杂度降低到n，怎么做呢，很简单，因为如果满足条件的元素存在，那么它的出现次数肯定是大于一半的，无论对于奇数个数数组还是偶数个数数组来说，出现次数大于一半，那么它都比其它元素出现的次数加起来还要多，所以设置两个值，一个用来保存数组中的值，一个用来保存次数。
然后如果下一个遍历到的数字与之前保存的数字相同，那么次数加一，否则次数减一，当次数为0的时候，保存当前遍历到的数字，将count置为1，如果存在满足条件的数字，那么最后可你的那个是该数字将count置为1，只需要检验count是否为1，不为1，输出0，为一继续进行检验，看该元素是否满足条件，满足则输出该数字，不满足输出0。
#code
class Solution {public:int MoreThanHalfNum_Solution(vector<int> numbers) {if(numbers.size()==0)return 0;int num=numbers[0];int count=1;for(int i=1;i<numbers.size();i++){if(count==0){num=numbers[i];count++;}else{if(num==numbers[i])count++;elsecount--;}}if(count==0)return 0;else{count=0;for(int i=0;i<numbers.size();i++){if(num==numbers[i])count++;}if(count>=(numbers.size()/2+1))return num;return 0;}return 0;}};
#思路
第三种则是利用快排的思想，如上面所说，出现次数超过一半，肯定是中位数，根据快排的思想，随机选择一个数，比它大的放在右边，比它小的放在左边，那么如果选中的数字刚好下标为n/2,那么肯定就是要找的中位数，如果下标小于n/2，那么往右边接着寻找，否则往左边接着寻找，利用一个递归的过程，肯定是可以找到n/2下标这个元素的，而且它的速度肯定要比全部排好序更快，然后将下标为n/2的元素作为结果进行检验。
#code
class Solution {public:int slecet(vector<int>&a,int l,int r){int mid=l+((r-l)>>1);if ( a[ l ] > a[ mid ] )swap( a[ l ], a[ mid ] );if ( a[ l ] > a[ r ] )swap( a[ l ], a[ r ] );if ( a[ mid ] > a[ r ] )swap( a[ mid ], a[ r ] );/* A[ Left ] <= A[ Center ] <= A[ Right ] */swap( a[ mid ], a[ r-1 ] ); /* 将pivot藏到右边，节约一次比较，反正都比过了 *//* 只需要考虑 A[ Left+1 ] … A[ Right–2 ] */return a[ r-1 ]; /* 返回 pivot */}int partition(vector<int>&a,int l,int r,int mid){if(l>=r)return mid;if(r-l==1)//一定要加上这一个判断条件，因为我们用了slecet函数选择元素，会导致只有两个元素的时候归并失效。{if(a[r]>=a[l])return mid;elseswap(a[l],a[r]);return mid;}int num=slecet(a,l,r);int i=l+1;int j=r-2;while(i<j){while(i<j&&a[i]<=num)//i++;while(j>i&&a[j]>=num)//可以往j--;if(i<j){swap(a[i],a[j]);}elsebreak;}swap(a[r-1],a[i]);return i;}int MoreThanHalfNum_Solution(vector<int> numbers) {if(numbers.size()==0)return 0;int mid=numbers.size()>>1;int start=0;int end=numbers.size()-1;int index=partition(numbers,start,end,mid);while(index!=mid){if(index>mid){end=index-1;index=partition(numbers,start,end,mid);}else{start=index+1;index=partition(numbers,start,end,mid);}}int num=numbers[mid];int count=0;for(int i=0;i<numbers.size();i++){if(num==numbers[i])count++;}if(count>=(numbers.size()/2+1))return num;return 0;}};
如果觉得《剑指offer数组中出现次数超过一半的数字》对你有帮助，请点赞、收藏，并留下你的观点哦！
