2021/3/11 剑指 Offer 39. 数组中出现次数超过一半的数字

题目描述

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

示例

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

解题思路

1. 看完题目第一感觉就是计数排序，计数超过数组长度一般的立刻结束并返回这个元素。不过会有一个弊端。当数组中的元素一个数值非常大一个数值非常小，会导致数组长度超出并报错。
2. 摩尔投票法：定义一个众数 num，最开始是数组第一个元素，一个得票数 votes。若当前遍历的数等于 num，那么 votes + 1，否则 votes - 1。如果得票数 votes 为 0，那么众数 num 变为当前的下一个元素。

Java代码实现

1. 可能导致异常的计数排序算法

class Solution {
    public int majorityElement(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > max) max = nums[i];
            else if (nums[i] < min) min = nums[i];
        }
        int[] countableArray = new int[max - min + 1];
        int pivot = nums.length >> 1;
        int res = 0;
        for (int i = 0; i < nums.length; ++i) {
            int cur = ++countableArray[nums[i] - min];

            if (cur > pivot) {
                res = nums[i];
                break;
            }
        }
        return res;
    }

}

2. 摩尔投票法

class Solution {
    public int majorityElement(int[] nums) {
        int num = nums[0];
        int votes = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] == num) {
                ++votes;
            } else {
                --votes;
                if (votes == 0 && i + 1 < nums.length) {
                    num = nums[i + 1];
                }
            }
        }
        return num;
    }
}