题解 | 数组中出现次数超过一半的数字

1、解题思路

摩尔投票法：假设第一个数字为候选数字，计数器初始化为1。遍历数组，如果当前数字与候选数字相同，计数器加1；否则计数器减1。如果计数器减到0，更换候选数字为当前数字，并将计数器重置为1。最后剩下的候选数字即为所求。时间复杂度：O(n)，空间复杂度：O(1)。
哈希表法：使用哈希表统计每个数字的出现次数。遍历哈希表，找到出现次数超过数组长度一半的数字。时间复杂度：O(n)，空间复杂度：O(n)。不符合题目对空间复杂度 O(1) 的要求。
排序法：将数组排序，中间位置即为所求。时间复杂度：O(nlogn)，空间复杂度：O(1)（如果使用原地排序）。不符合题目对时间复杂度 O(n) 的要求。
分治法：将数组分成两部分，分别求解多数元素。如果两部分的多数元素相同，即为所求；否则，遍历数组统计两者的出现次数。时间复杂度：O(nlogn)，空间复杂度：O(logn)（递归栈）。不符合题目对时间复杂度和空间复杂度的要求。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型vector
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        // write code here
        int candidate = numbers[0];
        int cout = 1;
        for (int i = 1; i < numbers.size(); ++i) {
            if (numbers[i] == candidate) {
                ++cout;
            } else {
                --cout;
                if (cout == 0) {
                    candidate = numbers[i];
                    cout = 1;
                }
            }
        }
        return candidate;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        int candidate = numbers[0];
        int count = 1;
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] == candidate) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    candidate = numbers[i];
                    count = 1;
                }
            }
        }
        return candidate;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        candidate = numbers[0]
        count = 1
        for num in numbers[1:]:
            if num == candidate:
                count += 1
            else:
                count -= 1
                if count == 0:
                    candidate = num
                    count = 1
        return candidate

3、复杂度分析

摩尔投票法：核心思想是通过抵消不同的数字，最终剩下的数字即为所求。算法正确性依赖于题目保证存在出现次数超过一半的数字。
效率：时间复杂度：O(n)，因为只需要遍历数组一次。空间复杂度：O(1)，仅需常数级别的额外空间。
边界条件：数组长度为1时，直接返回该元素。题目保证有解，因此无需额外的验证步骤。
适用性：摩尔投票法是解决此类问题的最优解，尤其适用于大规模数据。如果题目不保证存在解，需要额外遍历数组验证候选数字的出现次数。