C++ 5 lines, using stack


  • 6

    Basically, maintain a stack for comparing two adjacent number.
    Iterate the array left to right, if current stack is empty or the current number is the same as the top of stack, push the number to stack for next comparison.
    Otherwise, if the stack's top is different than the current number, do pop operation.

    Time is O(n), worst-case scenario, space is n/2

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            stack<int> S;
            for(int i = 0; i < nums.size(); i++){
                if(S.empty() || nums[i] == S.top()) S.push(nums[i]);
                else if(nums[i] != S.top()) S.pop();
            }
            return S.top();
        }
    };

  • 0
    M

    Not typical, but good idea!


  • 0

    Thanks for your courage ^_^


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.