C++ O(n) time solution with O(1) space


  • 0
    M

    class Solution {
    public:
    int majorityElement(vector<int>& nums) {
    int n = nums.size();
    int lastOne = nums[0];
    int cnt = 1;
    for(int i = 1;i<n;++i)
    {

            if(nums[i]!=lastOne)
                --cnt;
            else
                ++cnt;
            if(cnt == 0)
            {
                lastOne = nums[i];
                ++cnt;
            }
        }
        return lastOne;
    }
    

    };


Log in to reply
 

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