我正在解决这个问题,看到一些帖子后,我找到了一个使用摩尔投票算法时间复杂度为O(n)的解决方案。 多数元素是指出现次数超过数组大小一半的元素。 以下是我的o(lg n)时间复杂度代码,请建议它是否符合o(lg n)。 由于我刚开始学习编程,欢迎提出建议。
#include <bits/stdc++.h>
#include <algorithm>
using namespace std ;
int binarySearch(vector <int> a, int l, int h){
if(l - h < a.size() / 2)
return -1;
int mid = (l+h)/2;
int temporaryLow = mid;
int temporaryHigh = mid;
while(temporaryLow > 0 && a[temporaryLow] == a[mid])
temporaryLow--;
while(temporaryHigh < a.size() && a[temporaryHigh] == a[mid])
temporaryHigh++;
if((temporaryHigh -1) - (temporaryLow+1) +1 >= a.size()/2){
return a[mid];
}else{
return max(binarySearch(a,0,temporaryLow),binarySearch(a,temporaryHigh,h));
}
}
int findMajority(vector <int> numbers){
return binarySearch(numbers , 0, numbers.size());
}
int main()
{
int n ;
vector <int> a ;
while ((cin >> n) && n != 9999)
a.push_back(n);
int majority = findMajority(a);
cout << majority ;
}