39. 数组中出现次数超过一半的数字

Leetcode

题目描述

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

解题思路

多数投票问题，可以利用多数投票算法（Boyer-Moore Majority Vote Algorithm）来解决这个问题，时间复杂度为 O(N)，空间复杂度为 O(1)。

思路是让不同的数两两抵消。majority 记录候选值，cnt 记录它还没被抵消的次数：cnt 为 0 时把当前元素作为新的候选，之后遇到相同的数 cnt 加 1，不同的数 cnt 减 1。设出现次数超过一半的数为 x，每次抵消消耗两个不同的数，x 最多被其它数抵消的次数少于它自己的出现次数，因此最后留下的候选一定是 x。

例如 [3, 1, 3, 2, 3]：3 与 1 抵消，3 与 2 抵消，最后剩下的 3 就是答案。

第二次遍历统计候选的出现次数，用于题目不保证存在这样的数时（牛客的版本不存在时返回 0）；力扣的版本保证存在，可以省略。

public int inventoryManagement(int[] stock) {
    int majority = stock[0];
    int cnt = 0;
    for (int val : stock) {
        if (cnt == 0)
            majority = val;
        cnt += val == majority ? 1 : -1;
    }
    cnt = 0;
    for (int val : stock) {
        if (val == majority) {
            cnt++;
        }
    }
    return cnt > stock.length / 2 ? majority : 0;
}