Given an array of length n, calculate the majority element, which is the element which appears >= n/2 + 1, with time complexity O(n) and space complexity of O(1)

We will sweep down the sequence starting at the pointer position shown above.

As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.

When we move the pointer forward over an element e:

1. If the counter is 0, we set the current candidate to e and we set the counter to 1.
2. If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

When we are done, the current candidate is the majority element, if there is a majority.

 1type Vote struct {
 2	Candidate int
 3	Vote      int
 4}
 5
 6func MajorityElement(nums []int) int {
 7	vote := new(Vote)
 8	for _, v := range nums {
 9		if vote.Vote == 0 {
10			vote.Candidate = v
11			vote.Vote = 1
12			continue
13		}
14		if v == vote.Candidate {
15			vote.Vote++
16		} else {
17			vote.Vote--
18		}
19	}
20
21	return vote.Candidate
22}

References

• https://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html