unordered_map <int, int> count;

int MajorityElement(vector<int> &num) {

size_t n = num.size();

// O(n)

for(int i = 0; i < n; ++i) {

count[num[i]]++;

if(count[num[i]] > (n / 2)) {

return num[i];

}

}

/* O(nlogn)

}

int n = nums.size();

int majorityIndx = 0, count = 1;

for(int i = 1; i < n; ++i) {

if(nums[i] == nums[majorityIndx]) {

++count;

} else {

--count;

}

if(count == 0) {

majorityIndx = i;

count++;

}

}

return majorityIndx;