def majorityElement(nums):
    count_dict = {}
    n = len(nums)
    for num in nums:
        # 更新计数
        count_dict[num] = count_dict.get(num, 0) + 1
        # 检查是否已成为多数元素
        if count_dict[num] > n // 2:
            return num

def majorityElement(nums):
    nums.sort() # 对数组进行排序
    return nums[len(nums) // 2] # 返回中间的元素

def majorityElement(nums):
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            # 当前没有候选人，或者之前的票已抵消完，重新选择候选人
            candidate = num
        # 判断当前数字是否支持候选人
        if num == candidate:
            count += 1
        else:
            count -= 1

    # 题目假设总是存在多数元素，所以candidate就是答案
    return candidate

好的，我们这次来详细讲解 LeetCode 第 169 题：多数元素（Majority Element） 。 这道题非常经典，它考察的是数组和计数技巧，并且有一个非常巧妙的 Boyer-Moore 投票算法 ，可以在 O(n) 时间复杂度和 O(1) 空间复杂度内解决。 1. 题目描述 题目链接 ：LeetCode 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 * 10^4 -10^9 <= nums[i] <= 10^9 2. 题目理解与思路分析 首先，我们来明确题目的核心要求： 数组中一定存在一个 多数元素 。 这个元素的出现次数严格超过数组长度的一半。 这意味着什么？我们来看一个例子： 数组 [2,2,1,1,1,2,2] ，长度 n = 7 ， ⌊ n/2 ⌋ = 3 。多数元素的出现次数必须 大于 3 ，即至少为 4 次。 在这个数组中，元素 2 出现了 4 次，所以它是多数元素。 关键洞察 ：由于多数元素的个数比其他所有元素的总和还要多，那么如果我们把多数元素看作一个阵营，其他所有元素看作另一个阵营，进行“两两抵消”，最后剩下的一定是多数元素。 3. 循序渐进讲解解法 我们从最直观的方法开始，逐步优化。 方法一：哈希表计数（最直观） 这是最容易想到的方法。 思路 ： 遍历数组，用一个哈希表（字典）来记录每个数字出现的次数。 在遍历的同时，检查当前数字的出现次数是否已经超过了 n/2 。 一旦发现某个数字的次数超过 n/2 ，立即返回该数字。 代码示例（Python） ： 复杂度分析 ： 时间复杂度 ：O(n)。我们只遍历了数组一次。 空间复杂度 ：O(n)。最坏情况下（当所有元素都不同时），哈希表需要存储 n 个键值对。 评价 ：这个方法简单有效，在大多数情况下已经足够好。但面试官可能会追问：“你能在不使用额外空间（O(1) 空间）的情况下解决吗？” 方法二：排序法 思路 ： 由于多数元素出现的次数超过一半，那么当我们将数组排序后，位于数组 正中间 的元素（即索引为 n//2 的元素）一定是多数元素。 为什么？ 想象一下，多数元素的数量超过一半，那么无论这些元素在数组中的初始位置如何，当它们按顺序排列后，数组的中间位置必然会被这个多数元素所占据。 例子 ： nums = [2,2,1,1,1,2,2] -> 排序后为 [1,1,1,2,2,2,2] 。 长度 n=7 ，中间索引是 7//2 = 3 。 nums[3] = 2 ，正是多数元素。 代码示例（Python） ： 复杂度分析 ： 时间复杂度 ：O(n log n)。这取决于排序算法的时间复杂度（如快速排序、归并排序）。 空间复杂度 ：O(1) 或 O(n)。这取决于排序算法是否使用额外空间。在 Python 中， sort() 方法是原地排序，空间复杂度为 O(1)。 评价 ：代码极其简洁，但时间复杂度比哈希表法差。有没有方法能在 O(n) 时间和 O(1) 空间内解决？ 方法三：Boyer-Moore 多数投票算法（最优解） 这就是本题的精髓所在。它模拟了“两两抵消”的过程。 算法步骤 ： 初始化： 设置一个 candidate （候选人）变量，初始值可以为任意值（比如 None ）。 设置一个 count （计数）变量，初始化为 0。 遍历数组中的每一个元素： 当 count 为 0 时，我们选择当前的数字 num 作为新的 candidate 。 如果当前的数字 num 等于 candidate ，那么 count 加 1（表示支持者增加）。 如果当前的数字 num 不等于 candidate ，那么 count 减 1（表示一个支持者与一个反对者同归于尽）。 遍历结束后， candidate 就是我们要找的多数元素。 为什么这个算法有效？ 核心思想：由于多数元素的数量比其他所有元素的总和还要多，所以即使在最坏的情况下（多数元素每次都被其他元素“抵消”），最后剩下的也一定是多数元素。 这个过程就像一场选举，多数阵营的票数最终会胜出。 让我们用一个例子来一步步模拟 ： nums = [2, 2, 1, 1, 1, 2, 2] | 步骤 | 当前数字 (num) | 操作前的 count | 操作前的 candidate | 操作说明 | 操作后的 count | 操作后的 candidate | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 1 | 2 | 0 | (None) | count为0，选2为candidate，count+1 | 1 | 2 | | 2 | 2 | 1 | 2 | 数字等于candidate，count+1 | 2 | 2 | | 3 | 1 | 2 | 2 | 数字不等于candidate，count-1 | 1 | 2 | | 4 | 1 | 1 | 2 | 数字不等于candidate，count-1 | 0 | 2 | | 5 | 1 | 0 | 2 | count为0，选1为candidate，count+1 | 1 | 1 | | 6 | 2 | 1 | 1 | 数字不等于candidate，count-1 | 0 | 1 | | 7 | 2 | 0 | 1 | count为0，选2为candidate，count+1 | 1 | 2 | 最终结果 ： candidate = 2 ，正确。 代码示例（Python） ： 复杂度分析 ： 时间复杂度 ：O(n)。只需要一次线性扫描。 空间复杂度 ：O(1)。只使用了两个变量 count 和 candidate 。 评价 ：这是本题的最优解法，完美满足了所有要求。 4. 总结与比较 | 方法 | 时间复杂度 | 空间复杂度 | 核心思想 | 优点 | 缺点 | | :--- | :--- | :--- | :--- | :--- | :--- | | 哈希表法 | O(n) | O(n) | 计数统计 | 直观，易于理解 | 需要额外O(n)空间 | | 排序法 | O(n log n) | O(1) 或 O(n) | 中位数特性 | 代码极其简洁 | 时间复杂度较高，修改了原数组 | | Boyer-Moore投票法 | O(n) | O(1) | 抵消思想 | 时间空间最优 | 理解起来需要一些思考 | 推荐 ：在面试中，如果你能清晰地讲解并实现 Boyer-Moore 投票算法 ，会给面试官留下非常好的印象。你可以先提出哈希表法，然后分析其缺点，再引出这个巧妙的算法。 希望这个从易到难、逐步深入的讲解能让你彻底理解「多数元素」这道题！