Majority Element

Given an array of sizen, find the majority element. The majority element is the element that appearsmore than⌊ n/2 ⌋times.

You may assume that the array is non-empty and the majority element always exist in the array.

Brainstorm

Approach #1: Sort and Return Middle Element

int majorityElement(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size()/2];
}

Time complexity: $$O(n log n)$$

C++'s STL sort takes O(n log n) time, and returning the middle element is constant time.

Space complexity: $$O(n log n)$$

STL sort takes O(n log n) space.

Approach #2: Divide and Conquer

int helper(vector<int>& nums, int left, int right) {
    if (left == right)
        return nums[left];

    int mid = left + ((right - left) / 2);
    int majority1 = helper(nums, left, mid);
    int majority2 = helper(nums, mid + 1, right);

    if (majority1 == majority2) 
        return majority1;
    return count(nums.begin() + left, nums.begin() + right + 1, majority1) > count(nums.begin() + left, nums.begin() + right + 1, majority2) ? majority1 : majority2;

}
int majorityElement(vector<int>& nums) {
    return helper(nums, 0, nums.size()-1);
}