代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <ctime>
using namespace std;
int GetNumOfIndex(vector<int> & arr, int p, int r, int nIndex)
{
if (p >= r) return -1;
srand((unsigned int)time(NULL));
swap(arr[rand() % (r-p) + p], arr[r-1]);
int k = p;
for (int i=p; i<r-1; ++i) {
if (arr[i] < arr[r-1]) {
swap(arr[i], arr[k]);
++k;
}
}
swap(arr[k], arr[r-1]);
if (k == nIndex) return arr[k];
else if (k < nIndex)
return GetNumOfIndex(arr, k+1, r, nIndex);
else
return GetNumOfIndex(arr, p, k, nIndex);
}
int Calculate(const vector<int> & arr)
{
if (arr.empty()) return 0;
int l = arr.size(); // arr size
int ln1 = (l-1) / 2;
int ln2 = ln1 + (l-1) % 2;
vector<int> arrTemp(arr.begin(), arr.end());
int nNum1 = GetNumOfIndex(arrTemp, 0, arrTemp.size(), ln1);
int nNum2 = GetNumOfIndex(arrTemp, ln1, arrTemp.size(), ln2);
int nNum1Count = 0;
int nNum2Count = 0;
for (int i=0; i<l; ++i) {
if (arr[i] == nNum1) ++nNum1Count;
else if (arr[i] == nNum2) ++nNum2Count;
}
if (nNum1Count * 2 >= l) return nNum1;
else if (nNum2Count * 2>= l) return nNum2;
else return 0;
}
int Calculate2(const vector<int> & arr)
{
if (arr.empty()) return 0;
int nNum = arr[0];
int nCount = 1;
int l = arr.size(); // arr size
for (int i=1; i<l; ++i) {
if (arr[i] == nNum) ++nCount;
else {
--nCount;
if (nCount == 0) {
nNum = arr[i];
nCount = 1;
}
}
}
int nCount2 = 0;
for (int i=0; i<l; ++i) {
if (arr[i] == nNum) ++nCount2;
}
return nCount2 * 2 >= l ? nNum : 0;
}
int main(int argc, char ** argv)
{
vector<int> arr = {1, 2, 3, 2, 2, 5, 5, 2};
time_t t1 = time(NULL);
for (int i=0; i<1000000; ++i) {
Calculate(arr);
}
time_t t2 = time(NULL);
cout << t2 - t1 << endl;
t1 = time(NULL);
for (int i=0; i<1000000; ++i) {
Calculate2(arr);
}
t2 = time(NULL);
cout << t2 - t1 << endl;
return 0;
}