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.

Example 1:

```Input: nums = [3,2,3]
Output: 3
```

Example 2:

```Input: nums = [2,2,1,1,1,2,2]
Output: 2
```

Constraints:

• `n == nums.length`
• `1 <= n <= 5 * 104`
• `-231 <= nums[i] <= 231 - 1`

Solution 1: (Hash Table)

• Time Complexity : O(n)
• Space Complexity : O(n)
``````/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let map = new Map();
for (let num of nums) {
map.set(num, (map.has(num) ? map.get(num) : 0)  + 1);
if (map.get(num) > nums.length / 2) return num;
}
return -1;
};``````

Solution 2: (Sorting)

• Time Complexity : O(n)
• Space Complexity : O(1)
``````var majorityElement = function(nums) {
nums.sort();
return nums[Math.floor(nums.length / 2)];
};``````

Solution 3: (Divide and conquer)

• Time Complexity : O(nlogn)
• Space Complexity : O(logn)
``````var majorityElement = function(nums) {
return majority(nums, 0, nums.length - 1);
};

function majority(nums, l, r) {
if (l === r) return nums[l];
const mid = l + Math.floor((r - l) / 2);
const left = majority(nums, l , mid);
const right = majority(nums, mid + 1, r);
if (left === right) return left;
return nums.slice(l, r + 1).filter(x => x === left).length >
nums.slice(l, r + 1).filter(x => x === right).length
? left : right;
}``````