Majority Element

1. Problem Description

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

You may assume that the array is non-empty and that the given array always contains a majority element.

2. Approach

1. Approach 1
   • Use a map to count each element
   • Traverse the map to find the element whose count is >n/2
2. Approach 2
   • Traverse the array. If the current number is the same as the next number, increment the count by 1; otherwise decrement it by 1. When it reaches 0, start again
   • Traverse again and count this number to check whether it is >n/2

3. Implementation

3.1. map

func majorityElement(nums []int) int {
    count := make(map[int]int, 0)
    for _, num := range nums {
        count[num]++
    }
    for k,v := range count {
        if v > len(nums)/2 {
            return k
        }
    }
    return 0
}

3.2. Same +1, Different -1

func majorityElement(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	count := 1
	num := nums[0]
	for i := 1; i < len(nums); i++ {
		if num == nums[i] {
			count++
		}else {
			count--
        }
        if count == 0 {
            num = nums[i]
            count = 1
        }

	}
	count = 0
	for _, val := range nums {
		if val == num  {
			count++
		}
	}
	if count > len(nums) /2 {
		return num
	}
	return 0
}

4. References

• 169. Majority Element - LeetCode