int majorityElement(vector<int> &num)
{
int index = 0;
int cnt = 0;
for (int i = 0; i < num.size(); i++)
{
if (num[i] == num[index])
cnt++;
else
{
cnt;
if (cnt < 0)
{
cnt = 0;
index = i;
}
}
}
return num[index];
}
My linear solution (cpp).

Yes, this algorithm is pretty cool, and all is credited to Boyer & More from University of Texas at Austin.
You guys can take a look at the paper here.
Below is the java implementationpublic class Solution { public int majorityElement(int[] num) { int vote = num[0]; int count = 1; for(int i = 1; i < num.length; i++){ if(count == 0) { vote = num[i]; count++; } else if(vote != num[i]) count; else count++; } return vote; } }