169.md

169. Majority Element

Description

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.

Thinking Process

1. Keep a counter, initialize the counter to 0, initialize the target to nums[0]
2. Iterate through the array. If nums[i] == target, increase the counter, else decrease the counter by 1.
3. If counter becomes 0, reset the target to nums[i]

Code

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int target = nums[0];
        for(int num : nums){
            if(num == target)
                count++;
            else{
                target = count == 0 ? num : target;
                count = count == 0 ? 1 : count - 1;
            }
        }
        return target;
    }
}

Complexity

1. Time complexity is O(n) as the array is iterated only once
2. Space complexity is O(1) as no additional data structures are used