一开始 老不对老不对，我以为是 把vevtor 换成数组就对了 我以为是这个问题呢 其实不是
原因竟然是 end=index-1; 这里要拿出来才行 不然就是不对 注意吧
class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { if(numbers.empty()) return 0; //最后那个字 一定是在排序的中间位置 //超过数组长度一般嘛 //不用完全排序 找到k位置 前面都比他小 后面都比他大即可 int length =numbers.size(); int middle= length/2; int start=0;int end=length-1; int index=partition(numbers,start,end); while(index!=middle) { if (index>middle) { end=index-1; index= partition(numbers,start,end); }else { start=index+1; index= partition(numbers,start,end); } } int result=numbers[middle]; //接下来要判断是否 这个数字没有满足大于数组一半的要求 int num=0; for(int i=0;i<length;i++) { if(numbers[i]==result) num++; } if(num>length/2) return result; else return 0; } public: int partition(vector<int> & numbers,int low,int high) { int pivotkey=numbers[low];//当参考值 while(low<high) { while(low<high&&numbers[high]>pivotkey) {high--;} swap(numbers[low],numbers[high]); while(low<high&&numbers[low]<=pivotkey) { low++;} swap(numbers[low],numbers[high]); } return low; } public: void swap(int &A,int &B) { int temp; temp=A; A=B; B=temp; } };
// ====================方法2==================== //这个比较复杂，就是下一值如果和当前值一致，count就+1,否则-1，如果为0，则舍弃记录当前值，改下一值，最后+1的值可能会超过一半 int MoreThanHalfNum_Solution2(int* numbers, int length) { if (CheckInvalidArray(numbers, length)) return 0; int result = numbers[0];//初试为第一个值 int times = 1;//初试为1 for (int i = 1; i < length; ++i) { if (times == 0)//改记录下一值 { result = numbers[i]; times = 1; } else if (numbers[i] == result) times++; else times--; } if (!CheckMoreThanHalf(numbers, length, result)) result = 0; return result; }
原文：https://www.cnblogs.com/cgy1012/p/11399276.html