剑指offer-day23

2022年04月29日

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

最简单的想法当然是用哈希表或者排序，但是最优解是一个算法，叫摩尔投票法。

算法的大致思想是：记录一个投票数，与众数相同则投票数+1，否则-1。因为众数的数量超过数组长度的一半，那么统计整个数组的投票数会大于0。知道这个规律后，唯一的问题是怎么确定一个数是众数。那么就涉及到了第二个规律：数组中的某部分的投票数总和为0，并不会影响整体的票数。现在可以假设数组的第一个元素是众数，向后遍历，遇到相同的数时票数+1，否则-1，如果遇到票数为0的情况，则放弃这一块的遍历情况，转而设置下一个数为众数…直到遍历完成，此时票数一定大于0，指向的数即为众数。

class Solution {
    public int majorityElement(int[] nums) {
        int vote = 0;
        int x = 0;
        for(int num : nums){
            // 当票数为0时，假设遍历至此的数为众数
            if(vote == 0){
                x = num;
            }
            // 如果后续遍历的数与该数相等，票数+1，否则-1
            if(x == num){
                vote++;
            }
            else{
                vote--;
            }
        }
        // 返回最后指向的数
        return x;
    }
}

构建乘积数组

提示了无法使用除法，那么只能使用乘法，最优解选择的方式是对原数组遍历两遍：第一遍只累乘在自己之前的数，第二遍则累乘在自己之后的数，这样就得到答案了。

class Solution {
    public int[] constructArr(int[] a) {
        // 特殊情况：a为空数组，返回空数组
        if(a.length == 0){
            return new int[0];
        }
        int[] b = new int[a.length];
        // 因为第一个数只有自己之后的数的累乘，所以将b的第一个数置为1
        b[0] = 1;
        // 遍历第一遍，b[i]的值都是在自己之前的数的累乘
        for(int i = 1; i < a.length; i++){
            b[i] = b[i - 1] * a[i - 1];
        }
        // 记录一个临时值，用来记录b[i]之后的数的累乘
        int tmp = 1;
        // 因为最后一个数只有自己之前的数的累乘，之前已经计算完毕，所以从倒数第二个数开始
        for(int i = a.length - 2; i >= 0; i--){
            tmp *= a[i + 1];
            b[i] *= tmp;
        }
        return b;
    }
}