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.

&nbsp;
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2

&nbsp;
Constraints:


	n == nums.length
	1 &lt;= n &lt;= 5 * 104
	-109 &lt;= nums[i] &lt;= 109


&nbsp;
Follow-up: Could you solve the problem in linear time and in O(1) space?
class Solution(object):
    def majorityElement(self, nums):
        sol = None
        cnt = 0
        for i in nums:
            if cnt == 0:
                sol = i
            cnt += (1 if i == sol else -1)
        return sol
class Solution {
    public int majorityElement(int[] nums) {
        // Base case...
        if (nums.length == 1) {
            return nums[0];
        }
        // Sort nums array...
        Arrays.sort(nums);
        // Since the majority element appears more than n / 2 times...
        // The n/2 -th element in the sorted nums must be the majority element...
        return nums[nums.length / 2];
    }
}
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // Initialize sol and cnt to store the solution and its frequency for respective iterations...
        int sol = 0, cnt = 0;
        // For every element i in the array...
        for(int i = 0; i < nums.size(); i++ ) {
            // If cnt is equal to zero, update sol as sol = i
            if(cnt == 0){
                sol = nums[i];
                cnt = 1;
            }
            // If i is equal to candidate, increment cnt...
            else if(sol == nums[i]){
                cnt++;
            }
            // Otherwise, decrement cnt...
            else{
                cnt--;
            }
        }
        // Return & print the solution...
        return sol;
    }
};
var majorityElement = function(nums) {
    // Initialize sol and cnt to store the solution and its frequency for respective iterations...
    let sol = 0, cnt = 0;
    // For every element i in the array...
    for(let i = 0; i < nums.length; i++ ) {
        // If cnt is equal to zero, update sol as sol = i
        if(cnt == 0){
            sol = nums[i];
            cnt = 1;
        }
        // If i is equal to candidate, increment cnt...
        else if(sol == nums[i]){
            cnt++;
        }
        // Otherwise, decrement cnt...
        else{
            cnt--;
        }
    }
    // Return & print the solution...
    return sol;
};
Majority Element