详情

    隐含了一个线索：所有出现超过 ⌊ n/3 ⌋ 次的元素个数最多有 2 个
    在不考虑时间和空间复杂度的情况下，两次循环就能得出结果

    1. // 时间复杂度：O(n)，其中 n 为数组的长度。
    2. // 空间复杂度：O(n)，其中 n 为数组的长度，使用哈希表需要开辟额外的空间。
    3. func majorityElement(nums []int) (ans []int) {
    4.     length := len(nums)
    5.     need := length / 3
    6.     cnt := map[int]int{}
    7.     for _, v := range nums {
    8.         cnt[v]++
    9.     }
    10.     for v, c := range cnt {
    11.         if c > need {
    12.             ans = append(ans, v)
    13.         }
    14.     }
    15.     return
    16. }

    摩尔投票法 算法演示 概念

    func majorityElement(nums []int) (ans []int) {
    element1, element2 := 0, 0
    vote1, vote2 := 0, 0

    for _, num := range nums {
        if vote1 > 0 && num == element1 { // 如果该元素为第一个元素，则计数加1
            vote1++
        } else if vote2 > 0 && num == element2 { // 如果该元素为第二个元素，则计数加1
            vote2++
        } else if vote1 == 0 { // 选择第一个元素
            element1 = num
            vote1++
        } else if vote2 == 0 { // 选择第二个元素
            element2 = num
            vote2++
        } else { // 如果三个元素均不相同，则相互抵消1次
            vote1--
            vote2--
        }
    }

    cnt1, cnt2 := 0, 0
    for _, num := range nums {
        if vote1 > 0 && num == element1 {
            cnt1++
        }
        if vote2 > 0 && num == element2 {
            cnt2++
        }
    }

    // 检测元素出现的次数是否满足要求
    if vote1 > 0 && cnt1 > len(nums)/3 {
        ans = append(ans, element1)
    }
    if vote2 > 0 && cnt2 > len(nums)/3 {
        ans = append(ans, element2)
    }
    return
}