【剑指offer】39. 数组中出现次数超过一半的数字

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

题目描述

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

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

示例

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

解题思路1 排序

因为需要的数字出现次数多于一半，那么排序后必定在中间。

代码

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

解题思路2 HashMap

数数然后查找这种问题一定会想到HashMap，虽然执行效率不高，但是也算能出结果

代码2

class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length == 1) return nums[0];
        // 移位运算高级写法
        // int half = nums.length >> 1;
        int half = nums.length / 2;

        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            // 如果HashMap包含数组中的值，则先判断数量是否过半，如无过半，则数量加1
            // 不包含则创建一个新的Key和值为1的count
            if(map.containsKey(nums[i])){
                int count = map.get(nums[i]);
                if(++count > half){
                    return nums[i];
                }
                // map.remove(nums[i]);
                map.put(nums[i], count);
            }else{
                map.put(nums[i], 1);
            }
        }
        return -1;
    }
}

解题思路3 摩尔投票法

思想是将不同的数字互相消解，那最后余下的数字就是相同的数字。

用target记录上一次访问的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；如果不同count–，减到0的时候就要更换新的target值了，因为如果存在超过数组长度一半的值，那么最后target一定会是该值。可以这样理解，count的自加和自减就是在描述一种抵消关系，由于超过一半的出现次数，导致最后的target一定会是该值。（这种方法的时间复杂度自然会小些）

代码3

class Solution {
    public int majorityElement(int[] nums) {
        int target = nums[0]; // 初始化为数组的第一个元素，接下来用于记录上一次访问的值
        int count = 1; // 用于记录出现次数

        for(int i = 0; i < nums.length; i++){
            if(nums[i] == target){
                count++;
            }else{
                count--;
            }
            // 当count=0时，更换target的值为当前访问的数组元素的值，次数设为1
            if(count == 0){
                target = nums[i];
                count = 1;
            }
        }
        return target;
    }
}