Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Constraints:

n == nums.length

1 <= n <= 5 * 104

-231 <= nums[i] <= 231 - 1

v1.0

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> dic;
        int len = nums.size()/2;
        int i=0;
        while(i<nums.size()){
            if(dic.count(nums[i])){
                dic[nums[i]]++;
                if(dic[nums[i]]>len){
                    return nums[i];
                }
            }
            else{
                dic[nums[i]] = 1;
            }
            i++;
                
        }
        return nums[i-1];
            
    }
};

Runtime: 20 ms, faster than 59.38% of C++ online submissions for Majority Element.

Memory Usage: 19.7 MB, less than 9.83% of C++ online submissions for Majority Element.

v2.0

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int c=1;
        int ans=nums[0];
        for(int i=1 ; i<nums.size() ; i++){
            if(c==0){
                ans = nums[i];
            }
            if(ans == nums[i]){
                c++;
            }
            else{
                c--;
            }
        }
        return ans;
            
    }
};

Runtime: 20 ms, faster than 59.38% of C++ online submissions for Majority Element.

Memory Usage: 19.5 MB, less than 99.51% of C++ online submissions for Majority Element.