Virts

While brushing through simple problems on LeetCode, I came across a problem, LeetCode Problem 169, which has a straightforward description:

1. Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times in the array.
2. You may assume that the array is non-empty and that the majority element always exists in the given array.

Initially, I thought of sorting to find the median or finding the mode, but after looking at the solution, I realized there is a simpler solution.

The Boyer-Moore Voting Algorithm, which I saw described in the comments of the solution, feels very fitting: Mutual Destruction Elimination Method. The core idea is quite simple: maintain a number and its count. When the next number is the same as this number, its count increases by 1; otherwise, it decreases by 1. If the count becomes 0, replace this number with the next encountered number. Since there is always an element that appears more than ⌊ n/2 ⌋ times, we will definitely end up with a number whose count is greater than 0.

Here is the implementation of the Boyer-Moore Voting Algorithm in Golang to solve the above problem:

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

Although I feel that the applicability of this algorithm is somewhat narrow, as it cannot find the mode but can only find the element that appears more than n/2 times, the idea is indeed very clever. For solving this type of problem, it should be the most efficient, with a time complexity of $O(n)$ and a space complexity of $O(1)$.