图解LeetCode——剑指 Offer 39. 数组中出现次数超过一半的数字

一、题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

二、示例

2.1> 示例 1:

【输入】 [1, 2, 3, 2, 2, 2, 5, 4, 2] 【输出】 2

限制：

• • 1 <= 数组长度 <= 50000

三、解题思路

3.1> 利用哈希求解

根据题目描述，我们要找出数组中有一个数字出现的次数超过数组长度的一半，那么我们可以利用Map来存储每个数字的出现次数，即：key=数字，value=该数字出现的次数。然后，当我们发现某个数字的出现次数大于了总长度的一半，则直接return返回结果即可。

3.2> 利用摩尔投票法求解

除了上面介绍的哈希求解之外，我们也可以采用摩尔投票法。该投票法的操作步骤类似几个帮派的人混战，两个不同帮派的人只会采用同归于尽的方式去对战。那么假设某个帮派A的总人数是大于其他帮派（B、C、D），那么即使帮派BCD联合起来去跟帮派A对战，最终剩下的人一定是A帮派的人。那么，了解了摩尔投票法，我们可以举一个例子，即：nums=[1,2,3,2,2,2,5,4,2]，我们首先需要创建两个变量，分别是：winner和count，用于表示当前擂台上的擂主帮派和该帮派目前在擂台上的人数。现在我们从头开始遍历这个数组：

【遍历nums[0]时】winner=1，count=1； 【遍历nums[1]时】由于nums[1]不等于winner，所以count要减1，即：winner=1，count=0； 【遍历nums[2]时】由于count等于0，所以winner=nums[2]，并且count加1，即：winner=3，count=1； 【遍历nums[3]时】由于nums[3]不等于winner，所以count要减1，即：winner=3，count=0； 【遍历nums[4]时】由于count等于0，所以winner=nums[4]，并且count加1，即：winner=2，count=1； 【遍历nums[5]时】由于nums[5]等于winner，所以count加1，即：winner=2，count=2； ……

具体操作步骤，请见下图所示（更正一下：下图右上角不是“同归于尽”）：

四、代码实现

4.1> 利用哈希求解

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> mark = new HashMap();
        for (int num : nums) {
            int count = mark.getOrDefault(num, 0) + 1;
            if (count > nums.length / 2) return num;
            mark.put(num, count);
        }
        return -1;
    }
}

4.2> 利用摩尔投票法求解

class Solution {
    public int majorityElement(int[] nums) {
        int winner = 0, count = 0;
        for (int num : nums) {
            if (count == 0) winner = num;
            count += (winner == num) ? 1 : -1 ;
        }
        return winner;
    }
}