本文共 1962 字，大约阅读时间需要 6 分钟。
第二十一章数组中出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
//题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。 #include #include #include using namespace std; //第一种方法//hash法,时间O(n)，空间O(n)int Find(int *a,int N){ hash_map hm; int candidate; int maxTimes=INT_MIN; for(int i=0;i maxTimes){ maxTimes=hm[a[i]]; candidate=a[i]; } } return candidate;}//第二种方法//统计法，时间O(n),空间O(1)int Find2(int *a, int N) //a代表数组，N代表数组长度 { int candidate; int nTimes, i; for(i = nTimes = 0; i < N; i++) { if(nTimes == 0) { candidate = a[i], nTimes = 1; } else { if(candidate == a[i]) nTimes++; else nTimes--; } } return candidate; } //第三种方法//删除法,因为涉及到删除，数组不好操作，所以用容器处理int Find3(int *a,int N) //a代表数组，N代表数组长度 { vector num(a,a+N); for(auto it=num.begin();it!=num.end();){ auto n=next(it); for(;n!=num.end()&&n==it;++n); if(n==num.end())break; num.erase(n); it=num.erase(it); } return *num.begin();} int main() { int a[]={4,5,6,5,5,4,7,5,5}; cout<
加强版水王：找出出现次数刚好是一半的数字 //题目：找出出现次数刚好是一半的数字 #include #include #include using namespace std; //第一种方法//统计法，时间O(n),空间O(1)//将不看数组的最后一个元素，先将问题转化成了超过一半的数处理//最后一个元素无外乎两种情况，一种是最后一个元素不是这等于一半的数，那就不予考虑，以上得出的即是答案//最后一个元素即是这等于一半的数，上面得出的就不一定是解，那就统计该元素出现的次数int Find(int *a, int N) //a代表数组，N代表数组长度 { int candidate; int nTimes, i; for(i = nTimes = 0; i < N; i++) { if(nTimes == 0) { candidate = a[i], nTimes = 1; } else { if(candidate == a[i]) nTimes++; else nTimes--; } } int cnt=0; for(int i=0;i nTimes2?candidate1:candidate2;}int main() { int a[]={7,5,6,5,5,7,7,5}; cout<
转载地址：http://xbvvi.baihongyu.com/