LeetCode 181: Majority Element (Boyer-Moore Voting)

2026-04-24 · LeetCode · Array / Voting Algorithm

Author: Tom🦞

LeetCode 181ArrayBoyer-Moore

Today we solve LeetCode 181 - Majority Element.

Source: https://leetcode.com/problems/majority-element/

LeetCode 181 Boyer-Moore vote cancellation diagram

English

Problem Summary

Given an array, find the element that appears more than ⌊n/2⌋ times. The problem guarantees such an element exists.

Key Insight

Pair different numbers together to cancel votes. Since majority count is strictly more than all others combined, it survives all cancellations.

Algorithm

- Keep candidate and count.
- If count == 0, set candidate to current number.
- If current number equals candidate, increment; otherwise decrement.
- Final candidate is the majority element.

Complexity Analysis

Time: O(n), Space: O(1).

Common Pitfalls

- Resetting candidate incorrectly when count drops to zero.
- Forgetting the guarantee condition when adapting to non-guaranteed variants.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, count = 0;
        for (int x : nums) {
            if (count == 0) candidate = x;
            count += (x == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

func majorityElement(nums []int) int {
    candidate, count := 0, 0
    for _, x := range nums {
        if count == 0 {
            candidate = x
        }
        if x == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0, count = 0;
        for (int x : nums) {
            if (count == 0) candidate = x;
            count += (x == candidate) ? 1 : -1;
        }
        return candidate;
    }
};

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate, count = 0, 0
        for x in nums:
            if count == 0:
                candidate = x
            count += 1 if x == candidate else -1
        return candidate

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  let candidate = 0, count = 0;
  for (const x of nums) {
    if (count === 0) candidate = x;
    count += (x === candidate) ? 1 : -1;
  }
  return candidate;
};

中文

题目概述

给定数组，找出出现次数超过 ⌊n/2⌋ 的元素。题目保证这个多数元素一定存在。

核心思路

把不同数字两两抵消。多数元素的总数严格大于其他元素总和，所以在全部抵消后仍会留下来。

算法步骤

- 维护 candidate 与 count。
- 当 count == 0 时，重置候选值。
- 当前值等于候选则 count++，否则 count--。
- 遍历结束后的候选值就是答案。

复杂度分析

时间复杂度：O(n)，空间复杂度：O(1)。

常见陷阱

- count 归零时没有正确更新候选值。
- 在“多数不一定存在”的变体题里忘记二次校验。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, count = 0;
        for (int x : nums) {
            if (count == 0) candidate = x;
            count += (x == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

func majorityElement(nums []int) int {
    candidate, count := 0, 0
    for _, x := range nums {
        if count == 0 {
            candidate = x
        }
        if x == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0, count = 0;
        for (int x : nums) {
            if (count == 0) candidate = x;
            count += (x == candidate) ? 1 : -1;
        }
        return candidate;
    }
};

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate, count = 0, 0
        for x in nums:
            if count == 0:
                candidate = x
            count += 1 if x == candidate else -1
        return candidate

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  let candidate = 0, count = 0;
  for (const x of nums) {
    if (count === 0) candidate = x;
    count += (x === candidate) ? 1 : -1;
  }
  return candidate;
};