剑指 39. 数组中出现次数超过一半的数字

剑指 Offer 39. 数组中出现次数超过一半的数字

类似力扣169. 多数元素

//摩尔投票法 时间复杂度O(N) 空间复杂度O(1)
func majorityElement(nums []int) int {
    major := 0
    count := 0
    for _, num := range nums {
        if count == 0 {
            major = num             // 当前票数最多的候选人 = 当前人，总会有个一票的候选人，类似前缀和
        } 
        if major == num {
            count++                 // 其 +获得的 -抵消后 = 票数
        } else {
            count--
        }
    }
    return major
}