What is the time complexity of the Majority Element problem?

The time complexity depends on the approach used. The hash table approach is O(n), sorting is O(n log n), and the Boyer-Moore Voting Algorithm is O(n).

How do I solve Majority Element using Boyer-Moore Voting Algorithm?

The Boyer-Moore Voting Algorithm involves scanning the array while maintaining a count and a candidate element. When the count becomes 0, switch the candidate. This method has O(n) time complexity and O(1) space complexity.

Can the Majority Element problem be solved using sorting?

Yes, by sorting the array, the majority element will always appear in the middle of the array. This method has a time complexity of O(n log n).

What is the optimal space complexity for Majority Element?

The optimal space complexity is O(1), achieved by using the Boyer-Moore Voting Algorithm.

What is the Majority Element problem pattern?

The Majority Element problem involves scanning the array and using hash lookups or specialized algorithms like Boyer-Moore to find the element that appears more than n/2 times.

#169

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例 1：输入： nums = [3,2,3] 输出： 3 示例 2：输入： nums = [2,2,1,1,1,2…

数组哈希表分治排序计数

题目描述

给定一个大小为 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 * 10⁴
-10⁹ <= nums[i] <= 10⁹
输入保证数组中一定有一个多数元素。

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

lightbulb

解题思路

方法一：摩尔投票法

摩尔投票法的基本步骤如下：

初始化元素 $m$ ，并初始化计数器 $cnt=0$ 。接下来，对于输入列表中每一个元素 $x$ ：

如果 $cnt=0$ ，那么 $m=x$ 并且 $cnt=1$ ；
否则，如果 $m=x$ ，那么 $cnt = cnt + 1$ ，否则 $cnt = cnt - 1$ 。

一般而言，摩尔投票法需要对输入的列表进行两次遍历。在第一次遍历中，我们生成候选值 $m$ ，如果存在多数，那么该候选值就是多数值。在第二次遍历中，只需要简单地计算候选值的频率，以确认是否是多数值。由于本题已经明确说明存在多数值，所以第一次遍历结束后，直接返回 $m$ 即可，无需二次遍历确认是否是多数值。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Test the candidate's ability to implement the Boyer-Moore Voting Algorithm, which is an optimal solution for this problem.
question_mark
Look for understanding of time and space complexity, particularly when discussing the hash table or sorting approaches.
question_mark
Evaluate the candidate's problem-solving flexibility by asking about the trade-offs between different approaches.

warning

常见陷阱

外企场景

error
Misunderstanding the definition of majority element and thinking that the most frequent element is the majority.
error
Overcomplicating the solution with unnecessary extra space or sorting when simpler methods like the Boyer-Moore Voting Algorithm exist.
error
Forgetting that the problem guarantees the existence of a majority element, leading to unnecessary checks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the majority element in a stream of data where you can only access one element at a time.
arrow_right_alt
Extend the problem to find the majority element in multiple arrays combined.
arrow_right_alt
Modify the problem to work with an array where elements appear more than once but less than half the time.

help

常见问题

外企场景

继续练习

#347 前 K 个高频元素 #229 多数元素 II #594 最长和谐子序列