每日一题——数组中出现次数超过一半的数字

题目描述

给定一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如，输入一个长度为9的数组 [1, 2, 3, 2, 2, 2, 5, 4, 2]。由于数字 2 在数组中出现了5次，超过数组长度的一半，因此输出 2。

数据范围

• 数组长度：n ≤ 50000
• 数组元素值：0 ≤ val ≤ 10000
• 要求空间复杂度：O(1)
• 时间复杂度：O(n)

输入描述

• 输入保证数组非空，且保证有解。

输出描述

• 输出数组中出现次数超过一半的数字。

示例

示例1

输入：

[1,2,3,2,2,2,5,4,2]

返回值：

2

示例2

输入：

[3,3,3,3,2,2,2]

返回值：

3

示例3

输入：

[1]

返回值：

1

题解

解题思路

本题的关键在于找出数组中出现次数超过一半的数字。我们可以使用 摩尔投票算法 来高效解决这个问题。该算法的时间复杂度为 O(n)，且空间复杂度为 O(1)。

摩尔投票算法

摩尔投票算法的核心思想是通过对数组进行两次扫描，首先确定一个候选元素，然后验证这个候选元素是否满足条件。

步骤：

1. 第一遍扫描：我们用一个变量 candidate 来记录候选的数字，同时用一个 count 来记录当前候选数字的计数。如果遇到相同的数字，count 增加；如果遇到不同的数字，count 减少。当 count 为 0 时，更新 candidate 为当前数字，并重置 count 为 1。

2. 第二遍扫描：验证 candidate 是否真的超过了数组长度的一半。如果是，返回该数字，否则返回其他错误值（但本题保证必定有解）。

代码实现

#include <vector>
#include <iostream>
using namespace std;

int majorityElement(vector<int>& nums) {
    int candidate = -1, count = 0;

    // 第一遍扫描，找出候选元素
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
            count = 1;
        } else if (num == candidate) {
            count++;
        } else {
            count--;
        }
    }

    // 第二遍扫描，确认候选元素是否为多数元素
    count = 0;
    for (int num : nums) {
        if (num == candidate) {
            count++;
        }
    }

    return count > nums.size() / 2 ? candidate : -1; // 返回候选元素
}

代码解析

• 第一遍扫描：我们首先设定 candidate 为 -1，表示当前还没有候选数字。count 用来计数，初始值为 0。在遍历数组时，遇到与 candidate 相同的数字时增加 count，否则减少 count。当 count 为 0 时，说明当前数字可以成为候选数字，重置 candidate 为当前数字，count 为 1。

• 第二遍扫描：确认 candidate 是否真的是出现次数超过数组一半的数字。我们遍历数组，统计 candidate 的出现次数，最后检查它是否大于数组长度的一半。

时间与空间复杂度

• 时间复杂度：O(n)，需要两次遍历数组，分别为找候选数字和验证候选数字。
• 空间复杂度：O(1)，只用了常数空间来存储候选元素和计数。