题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：第一种方法是抵消的思路，如果一个数字在一个数组中出现的次数超过一半，那么一一抵消之后，最后剩下的一定是目标数字。一定要注意找到元素之后要验证是否该数字超过数组长度的一半。
维护两个变量，一个记数，一个保存数组元素，如果遍历到下一个数字的时候，和保存数字相同，则记数值加1，否则减1。注意这两个变量初始化，记数值开始为1，进入循环后如果变为0了，要重新赋值为1，并且保存值的变量也更新。
class Solution {public: bool checked(vector &numbers,int num){ //检测得到的答案是否合法，查过数组数量的一半 int len = 0; for(int i = 0;i < numbers.size();++i){ if(num == numbers[i]){ ++len; } } if(len <= (numbers.size() / 2)){ return false; } return true; } int MoreThanHalfNum_Solution(vector numbers) { if(numbers.empty()){ return 0; } int cnt = 1;//先初始化为1 int flag = numbers[0]; for(int i = 0;i < numbers.size();++i){ if(cnt == 0){ cnt = 1; flag = numbers[i]; } else if(flag == numbers[i]){ ++cnt; } else{ --cnt; } } if(checked(numbers,flag)){ return flag; } return 0; }}; 第二种思路是借鉴快速排序的方法，事实上可以不用对数组进行排序，或者说仅部分排序，受快速排序的partition函数的启发，我们可以利用反复调用partition函数来求的该数字。我们现在数组中随机选取一个数字，而后通过Partition函数返回该数字在数组中的索引index，如果index刚好等于n/2，则这个数字便是数组的中位数，也即是要求的数，如果index大于n/2，则中位数肯定在index的左边，在左边继续寻找即可，反之在右边寻找。这样可以只在index的一边寻找，而不用两边都排序，减少了一半排序时间。这种情况的平均时间复杂度大致为：T(n) = n+n/2+n/4+n/8+....+1，很明显当n很大时，T(n)趋近于2n，也就是说平均情况下时间复杂度为O(n),但是这种情况下，最坏的时间复杂度依然为O(n*n)，最坏情况下，index总是位于数组的最左或最右边，这样时间复杂度为T(n) = n+n-1+n-2+n-3+....+1 = n(n-1)/2，显然，时间复杂度为O(n*n)，空间复杂度为O(1)。
idx = partition(numbers,lo,hi);位置非常重要，下面这种在下题就有bug，这题没毛病，不过还是应该idx定义的时候写这个。
class Solution {public: int partition(vector &numbers,int lo,int hi){ int pos = lo + rand() % (hi - lo + 1); int pivot = numbers[pos]; swap(numbers[lo],numbers[pos]); while(lo < hi){ while(lo < hi){ //从右往左找第一个小于pivot if(numbers[hi] > pivot){ --hi; } else{ numbers[lo] = numbers[hi]; ++lo; break; } } while(lo < hi){ //从左往右找第一个大于pivot if(numbers[lo] < pivot){ ++lo; } else{ numbers[hi] = numbers[lo]; --hi; break; } } } numbers[lo] = pivot; return lo; } bool checked(vector &numbers,int flag){ int len = 0; for(int i = 0;i < numbers.size();++i){ if(numbers[i] == flag){ ++len; } } if(len <= (numbers.size() / 2)){ return false; } return true; } int MoreThanHalfNum_Solution(vector numbers) { if(numbers.empty()){ return 0; } int mid = numbers.size() / 2 ; int idx = 0; int lo = 0,hi = numbers.size() - 1; while(idx != mid){ idx = partition(numbers,lo,hi); if(idx < mid){ lo = idx + 1; } if(idx > mid){ hi = idx - 1; } } if(checked(numbers,numbers[idx])){ return numbers[idx]; } return 0; }};
正确版本：
class Solution {public: int partition(vector &numbers,int lo,int hi){ int pos = lo + rand() % (hi - lo + 1); int pivot = numbers[pos]; swap(numbers[lo],numbers[pos]); while(lo < hi){ while(lo < hi){ //从右往左找第一个小于pivot if(numbers[hi] > pivot){ --hi; } else{ numbers[lo] = numbers[hi]; ++lo; break; } } while(lo < hi){ //从左往右找第一个大于pivot if(numbers[lo] < pivot){ ++lo; } else{ numbers[hi] = numbers[lo]; --hi; break; } } } numbers[lo] = pivot; return lo; } bool checked(vector &numbers,int flag){ int len = 0; for(int i = 0;i < numbers.size();++i){ if(numbers[i] == flag){ ++len; } } if(len <= (numbers.size() / 2)){ return false; } return true; } int MoreThanHalfNum_Solution(vector numbers) { if(numbers.empty()){ return 0; } int mid = numbers.size() / 2 ; int idx = 0; idx = partition(numbers,lo,hi); int lo = 0,hi = numbers.size() - 1; while(idx != mid){ if(idx < mid){ lo = idx + 1; } if(idx > mid){ hi = idx - 1; } idx = partition(numbers,lo,hi); } if(checked(numbers,numbers[idx])){ return numbers[idx]; } return 0; }};