多数元素

多数元素

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

经典栈魔法。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        stack<int> s;
        for (int x: nums) {
            if (s.empty() || s.top() == x) s.push(x);
            else s.pop();
        }
        return s.top();
    }
};