Skip to main content

多数元素

题目

给定一个大小为 n 的数组, 找到其中的多数元素. 多数元素是指在数组中出现次数大于 n / 2 的元素. 你可以假设数组是非空的, 并且给定的数组总是存在多数元素.

示例

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

题解

使用摩尔投票算法(Boyer-Moore Voting Algorithm), 初始化一个 candidate 变量来存储候选多数元素，和一个 count 变量来记录计数。遍历数组:

如果 count 为 0, 我们将当前元素设为新的候选元素.
如果当前元素等于候选元素, 我们增加计数; 否则减少计数.

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  // 初始化第一个 num 为候选
  let cadidate = nums[0]
  // 那么初始化候选 num 的数量就是 1
  let count = 1

  for (let i = 1; i < nums.length; i++) {
    // 如果当前 num 是候选数字, 计数加一
    if (nums[i] === cadidate) {
      count++
    } else {
      // 如果 count 为 0, 说明候选数字要换了
      if (count === 0) {
        cadidate = nums[i]

        // 如果当前 num 是候选数字, 计数减一
      } else {
        count--
      }
    }
  }

  return cadidate
}

时间复杂度: O(n)
空间复杂度: O(1)

题目
题解