Let's define major element as element such that occurs in an array `> n / 2` times
To find it, we'll additionally store two variables: `cadidate` and `count`
Let's go through the array: if `count = 0` then we'll pick current element as a `cadidate`
If current element equals to candidate, we'll increase `count` by `1` and else decrease by `1`
So if we are guaranteed that input array contains major element, then it will be certainly found
Thus, we have algorithm `T(n)`, that uses `O(1)` additional space
Else, just do a simple check for candidate
Proof of correctness of that algorithm may be found here