int majorityElement(int num[], int n) {
int cnt = 0, res;
for (int i = 0; i < n; ++i) {
if (cnt == 0) res = num[i];
if (res == num[i]) ++cnt;
else --cnt;
}
return res;
}

The question assumes that the majority always exists. Anyway, you can check that if res is the majority by traversing the array one more time, it's still O(n) time.