Majority Element Cont…

Question: Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

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

Example 1:

Input: [3,2,3]
Output: 3

You may view the full question here.

Approach 2: Let’s try an approach without using maps. We sort the array and keep counting the elements. And when the count is greater than length/2, we return that element.

//Approach 2:
//Runtime: 3ms
//Memory usage: 41.4MB
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for(int i = 1; i<nums.length; i++){
            if(nums[i]==nums[i-1]){
                count++;
                if(count>=nums.length/2){
                    return nums[i];
                }
            } else {
                count = 0;
            }
        }
        return nums.length==0?0:nums[0];
    }
}

Approach 3: Here is another approach, again here, we sort the array. This time, instead of counting, we skip ahead and check if the (n/2 -1)th element is equal to the current element. This way, we have to check only half the array at max.

//Approach 3:
//Runtime: 2ms
//Memory usage: 41.5MB
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int jump = nums.length/2 - (nums.length%2==0?1:0);
        for(int i = 0, j = i+jump; j<nums.length; i++, j++){
            if(nums[i]==nums[j]){
                return nums[i];
            }
        }
        return 0;
    }
}

Find more posts here.

Cheers & Chao!