```
class Solution {
public:
int majorityElement(vector<int>& nums) {
vector<int>::iterator mid = nums.begin() + nums.size()/2;
nth_element(nums.begin(), mid, nums.end());
return (*mid);
}
};
```

note that nth_element is in `<algorithm>`

and runs in O(n) time.