代码如下：

#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;
}