📃 题目描述

题目链接：剑指 Offer 39. 数组中出现次数超过一半的数字 (opens new window)

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

🔔 解题思路

Boyer-Moore 投票算法：

想象一下，如果把这些数字当做人种，一个数字和另外一个数字打了起来，同归于尽。最后剩下的是不是人数最多的那种人。这里要满足一个条件：某类人的数目一定要大于总人数的一半

算法步骤：我们选择输入数组中第一个元素作为候选元素candidate，并设置其出现次数为count=1。随后遍历数组

• 当遇到与 candidate 相同的元素，count + 1，不同的元素，count - 1
• 当 count 为 0 的时候，选择下一个元素为候选元素，并且置 count= 1
• 遍历到数组的最后，剩下的 candidate 就是要求的结果

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        // candidate 出现次数
        int count = 1;

        for (int i = 1; i < nums.length; i ++) {
            if (candidate == nums[i]) {
                count ++;
            }
            else {
                count --;
            }

            if (count == 0) {
                candidate = nums[i + 1];
            }
        }

        return candidate;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：