Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

Follow-up: Could you solve the problem in linear time and in O(1) space?

给定一个大小为 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 * 104
  • -109 <= nums[i] <= 109

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

第一反应是分别计数，这种方法显然有点笨。。。

因为题目想找出现次数最多的数字（这种题目要求大于一半数量，说明肯定有大于一半数量存在的），其实可以这样，不用分别计数，而是按照顺序依次“增减”计数，比如：

1 1 2 2 1 1

最开始遇到1，遇到1就计数+1，遇到不是1就计数-1，如果这个数字大于一半数量，那么增增减减之后，一定也还是大于零

🥬上菜

在这个问题中，需要找到一个出现次数超过 ⌊n/2⌋ 次的多数元素。对于这种问题，有一种非常高效的解决方法，称为 Boyer-Moore 投票算法。这种算法可以在 O(n) 时间复杂度内找到多数元素，并且其空间复杂度为 O(1)。

Boyer-Moore 投票算法

其核心思想是通过一种巧妙的方式取消掉非多数元素的计数，来找到多数元素。具体步骤如下：

  1. 初始化：设置两个变量，candidate（候选人）初始化为任意值，count（计数）初始化为 0。
  2. 第一遍遍历：遍历数组 nums。
    • 如果 count 为 0，设当前元素为 candidate。
    • 如果当前元素等于 candidate，增加 count。
    • 否则减少 count。
  3. 第二遍遍历：验证 candidate 是否为多数元素（这一步在题目中可以省略，因为题目保证了总是存在多数元素）。
    • 计算 candidate 的出现次数。
    • 如果出现次数大于 ⌊n/2⌋，返回 candidate。

直觉的理解：

每次在找到两个不同的元素时就将它们“抵消”。如果一个元素的数量超过总数的一半，那么即使它与其他所有不同的元素进行抵消，最后仍然会剩余该元素，因为它的数量多于其他所有元素的总和。

但是要注意这个算法成立的关键前提：数组中存在一个多数元素，其出现次数严格大于数组长度的一半。

实现代码（C++）

// 169. Majority Element
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate;
        int count = 0;

        for (int num : nums) {
            // 说明增增减减之后又回到零
            if (count == 0) {
                candidate = num;
            }
            count += (candidate == num) ? 1 : -1;
        }

        // 由于题目限制，下面的判断可以省略（但其实很必要）
        // count = 0;
        // for (int num : nums) {
        //     if (num == candidate) {
        //         count++;
        //     }
        // }
        // if (count > nums.size() / 2) return candidate;

        return candidate;

    }
};