package main

func majorityElement(nums []int) int {
	// 摩尔投票法，左右对碰
	curr := -1
	count := 0
	n := len(nums)
	for i := 0; i < n; i++ {
		if count == 0 {
			// 当前一个元素碰没了的时候，碰撞主元素就可以换成当前元素了
			curr = nums[i]
		}
		if nums[i] == curr {
			count++
		} else {
			count--
		}
	}
	sum := 0
	for _, v := range nums {
		if v == curr {
			sum++
		}
	}
	if sum > len(nums)/2 {
		return curr
	}
	return -1
}

func main() {

}