题目

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：nums = [3,2,3]
输出：[3]

示例 2：

输入：nums = [1]
输出：[1]

示例 3：

输入：nums = [1,2]
输出：[1,2]

提示：

  • 1 <= nums.length <= 5 * 104
  • -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

思路

哈希表

第一反应是使用哈希表来存储每个元素出现的次数，然后遍历哈希表，找出出现次数超过 n/3 的元素。这个方法的时间复杂度是 O(n)，空间复杂度是 O(n)。

代码也简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func majorityElement(nums []int) []int {
	counts := make(map[int]int, len(nums))
	eles := make(map[int]struct{}, 2)
	for _, num := range nums {
		counts[num]++
		if counts[num] > len(nums)/3 {
			eles[num] = struct{}{}
		}
	}

	res := make([]int, 0, len(eles))
	for num := range eles {
		res = append(res, num)
	}

	return res
}

但是这个方法的空间复杂度是 O(n)，题目的进阶要求是空间复杂度 O(1)，所以考虑其他方法。

摩尔投票法

169. 多数元素

这里值得再看一下 169. 多数元素 这个题：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

当然直接使用哈希表也是可以的，这道简单题有相当多的解法，其中比较值得学习的是摩尔投票法（Boyer-Moore Voting Algorithm），它的核心思想是使用一个计数器来记录当前候选元素的出现次数，并在遍历数组时根据计数器的值来判断是否更新候选元素。

摩尔投票的本质是抵消，要理解这个算法，首要就是看待这些元素的方式。假设有一个数组 nums，其中包含两类元素 A 和 非A，只要 A 的数量大于 非A 的数量，那么 A 就是多数元素，所以 A 的数量减去 非A 的数量一定大于 0。基于此，还可以得到一个数组 nums，最多只能有一个多数元素（反证法：如果存在两个多数元素 A 和 B，那么 A 和 B 的数量之和一定大于 n，这与多数元素的定义矛盾）。

所以思路是：

  1. 先假设第一个元素（nums[0]）是候选元素(A)，计数器 count 初始化为 1。
  2. 遍历数组，遇到候选元素 A，计数器加 1；遇到非候选元素 B，计数器减 1。
  3. 如果计数器 count 减到 0，说明当前候选元素 A 的数量已经被抵消完了，重新选择下一个元素作为新的候选元素，计数器重置为 1。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func majorityElement(nums []int) int {
    candidate := nums[0]
    for i, count := 1, 1; i < len(nums); i++ {
        if count == 0 {
            candidate = nums[i]
            count = 1
            continue
        }

        if nums[i] == candidate {
            count++
        } else {
            count--
        }
    }

    return candidate
}

229. 多数元素 II

229. 多数元素 II 的思路和 169. 多数元素 是一样的，只不过这里的多数元素是出现次数超过 n/3 的元素，所以用反证法可以知道最多可以有两个候选元素。

并且根据题目要求，数组是非空的，并且给定的数组总是存在多数元素，所以只会存在两种情况，一种是只有一个候选元素，另一种是有两个候选元素。分别考虑这两种情况是是否都适合摩尔投票法：

  1. 只有一个多数元素：那数组的元素可以分为两类，A 和 非A，设 A 的数量为 k，非A 的数量为 n-k。非A 元素最多只能有 n-k 组（每组一个元素），最少有 2 组（最多为 n/3 个元素和 (n/3)-1 个元素）。
  2. 有两个多数元素：那数组的元素可以分为三类，A、B 和 非A、B，设 A 的数量为 k1，B 的数量为 k2，非A、B 的数量为 n-k1-k2。那么 非A、B 元素最多只能有 n-k1-k2 组（每组一个元素），最少有 1 组（最多为 (n/3)-2 个元素，k1 和 k2 的数量都为 (n/3)+1）。

使用抵消的思路来看这个问题，因为要求出现次数超过 n/3 的元素，所以需要每次选择 3 个互不相同的元素进行抵消，比如 [A, B, C, A, A, B, C]：

  • 前三个元素 A、B 和 C 进行相互抵消，得到的结果是 A: 0、B: 0、C: 0；
  • 第四、第五和第六个元素 A、A 和 B 进行相互抵消，得到的结果是 A: 2、B: 1；
  • 然后把上面的结果 A: 2、B: 1 和最后一个元素 C 进行相互抵消，得到的结果是 A: 1、B: 0、C: 0；

再比如有两个多数元素的例子 [A, B, B, C, B, C, A, A]：

  • 前三个元素 A、B 和 B 进行相互抵消，得到的结果是 A: 1、B: 2；
  • 前面的结果和第四个元素 C 进行相互抵消，得到的结果是 A: 1、B: 3；
  • 前面的结果和第五个元素 B 进行相互抵消，得到的结果是 A: 0、B: 2；
  • 前面的结果和第六元素 C 进行相互抵消，得到的结果是 B: 2、C: 1；
  • 前面的结果和第七个元素 A 进行相互抵消，得到的结果是 B: 1、C: 0；
  • 前面的结果和最后一个元素 A 进行相互抵消，得到的结果是 B: 1、A: 1；

可以看到用摩尔投票法的思路来解决这个问题是可行的，只不过对比 超过半数才是多数元素的算法 需要稍微改动一下。因为这里的多数元素是出现次数超过 n/3 的元素，所以最多只能有两个候选元素，然后分别设置计票器。当计票器为 0 时，说明当前候选元素的数量已经被抵消完了，需要重新选择候选元素。这里在实现的时候，要注意一个问题：什么时候需要更新候选元素？遍历到的元素会存在三种情况：

  1. 遇到候选元素 A：计票器 voteA 加 1。
  2. 遇到候选元素 B：计票器 voteB 加 1。
  3. 遇到非候选元素 C：计票器 voteA 和 voteB 都减 1。

注意这里当遇到候选元素 A 的时候是只对 voteA 加 1，而不对 voteB 减 1 操作的。

根据上面的思路，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func majorityElement(nums []int) []int {
    var candidate1, vote1, candidate2, vote2 int
    for _, num := range nums {
        if num == candidate1 && vote1 > 0 {
            vote1++
        } else if num == candidate2 && vote2 > 0 {
            vote2++
        } else if vote1 == 0 {
            candidate1 = num
            vote1 = 1
        } else if vote2 == 0 {
            candidate2 = num
            vote2 = 1
        } else {
            vote1--
            vote2--
        }
    }

    var count1, count2 int
    for _, num := range nums {
        if num == candidate1 {
            count1++
        } else if num == candidate2 {
            count2++
        }
    }

    results := make([]int, 0, 2)
    if count1 > len(nums)/3 {
        results = append(results, candidate1)
    }
    if count2 > len(nums)/3 {
        results = append(results, candidate2)
    }

    return results
}

上面的代码有几点值得注意：

  1. 这里的 vote1 和 vote2 都是计票器，分别对应两个候选元素 candidate1 和 candidate2。当计票器为 0 时，说明当前候选元素的数量已经被抵消完了，需要重新选择候选元素。
  2. 最后仍然需要遍历一遍数组，统计候选元素的数量。这是为了防止在最后的结果中出现 0 的情况，比如 [1, 2, 3]，这里的候选元素是 1 和 2，但是它们的数量都没有超过 n/3，所以最后的结果应该是 []。

通用化

根据上面的思路，可以把这个算法通用化，变成一个可以处理 k 个候选元素的算法。这里的 k 是最多的候选元素数量，比如 k=2 就是上面的实现，k=1 就是 169. 多数元素 的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func majorityElement(nums []int) []int {
	const k int = 2 // 这里的 k 是最多的候选元素数量
	candidates := make(map[int]int, k)
	for _, num := range nums {
		if len(candidates) < k {
			candidates[num]++
			continue
		}

		if _, ok := candidates[num]; ok {
			candidates[num]++
			continue
		}

		for candidate, vote := range candidates {
			if vote == 0 {
				delete(candidates, candidate)
				break
			}
		}

		for candidate, vote := range candidates {
			if vote == 1 {
				delete(candidates, candidate)
			} else {
				candidates[candidate]--
			}
		}
	}

	counts := make(map[int]int, len(candidates))
	for _, num := range nums {
		if vote, ok := candidates[num]; ok && vote > 0 {
			counts[num]++
		}
	}

	results := make([]int, 0, len(counts))
	for num, count := range counts {
		if count > len(nums)/(k+1) {
			results = append(results, num)
		}
	}

	return results
}