LeetCode 169. Majority Element

问题描述

给定一个数组，长度为 n，找到众数。众数是指出现次数大于「n/2」的元素。

假定数组非空，且众数一定存在。

栗 1：

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

栗 2：

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

解题思路

题目其实并不难，可以有很多种解法，比如：

• 使用 map 记录元素出现的次数
• 先排序，然后取中间位的元素
• ...

那为什么还要记录这道题目的解法呢？因为我在解法中看到了一个比较独特的思路，即摩尔投票算法。下面来介绍一下它的原理。

原理与实现

它的主要原理是将不同的数进行抵消，最终剩下的不能抵消的数则为所求结果。

具体实现如下：

• 用 array 记录不能被抵消的数，用 result 记录删除抵消数据对之后的结果。
• 遍历原数组，将元素与 array 中的数据进行比较。
  • 如果不相同，则可以抵消。更新 array 和 result，即在 array 和 result 中删除抵消的数据；
  • 如果相同，则不能抵消，元素加入到 array。
• 最后，array 和 result 中就是所求得的结果。

举例说明

举个栗子，比如数组 list = [1, 3, 1, 2, 1, 1]。下面来逐个遍历数组元素。

• 取出 1。由于初始 array = []，没有可以抵消的数。将 1 添加到 array，此时 array = [1], result = [1, 3, 1, 2, 1, 1]。
• 取出 3。由于 array = [1]， 1 与 3 不相等，可以抵消。此时 array = [], 在 result 中删除 1 和 3，result = [1, 2, 1, 1]。
• 取出 1。由于 array = []，将 1 添加到 array。此时 array =[1], result = [1, 2, 1, 1]。
• 取出 2。由于 array = [1]，2 与 1 不相等，可以抵消。此时 array = [], 在 result 中删除 1 和 2，result = [1, 1]。
• 取出 1。由于 array = []，将 1 直接添加到 array。此时 array = [1]，result = [1, 1]。
• 取出 1。由于 array = [1]，它们相同不能抵消，将 1 添加到 array。此时 array = [1, 1]，result = [1, 1]。

在这过程中，抵消掉了 (1,3)、(1,2) 两个数据对，所以还剩下 [1,1]。因此 1 为所求得的结果。

算法简化

在上述实现中，array 和 result 是我们为了方便理解算法假想出来的，其实并不需要。只需使用两个变量 majority 和 count 进行记录，来简化算法。

其中 majority 记录不能被抵消的元素，count 记录不能被抵消元素的个数。算法调整如下：

• 当 count == 0，说明没有可以被抵消的元素，那么 majority 更新为当前元素，count += 1。
• 当 count > 0，说明有可以被抵消的元素。如果当前元素与 majority 不等，则可以抵消，count -= 1；反之 count += 1。

最后的 majority 即为所求值。

代码实现

js 版代码实现如下：

var majorityElement = function(nums) {
  if (nums && nums.length > 0) {
    // 不能被抵消的数
    let majority = nums[0]

    // 记录不能抵消的数量
    let count = 1

    let i = 1
    while (i < nums.length) {
      const num = nums[i]

      // 没有可以抵消的，直接更新
      if (count === 0) {
        // 更新 majority
        majority = num
        count = 1
      } else {
        if (majority !== num) {
          // 可以抵消
          count -= 1
        } else {
          count += 1
        }
      }
      i += 1
    }

    return majority
  }
}

栗子重演

对应上面的栗子，我们再来走一遍流程：

• 取出 1。由于是数组第一个元素，此时设置 majority = 1，count= 1。
• 取出 3。由于它与 majority 不等，可抵消。此时，更新 count = 0，majority 更不更新无所谓，因为它有自己的更新时机。
• 取出 1。由于 count = 0，没有可以被抵消的元素。此时更新 majority = 1，count = 1。
• 取出 2。由于它与 majority 不等，可抵消。此时，更新 count = 0，同样，majority 保持不变。
• 取出 1。由于 count = 0，没有可以被抵消的元素。此时，更新 majority = 1，count = 1。
• 取出 1。它与 majority 相等，不可抵消。此时，更新 count = 2。

最后，majority = 1 即为结果。

参考资料：

• 如何理解摩尔投票算法