[数据结构与算法]键值offer java day23 数学

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

目标是数组值的众数

方1排序，众数在中间位置

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

方2:K神题解摩尔投票法

T2 66. 构建乘积数组

示例[1,2,3,4,5]

b[0] = 1*2*3*4*5 = 120

对角线分上下两个三角

class Solution {
    public int[] constructArr(int[] a) {
        int len =a.length,tmp=1;
        if(len==0) return new int[0]; //数组为空返回空
        int[] res = new int[len]; 
        res[0] = 1;
        for(int i=1;i<len;i++){
            res[i] = res[i-1]*a[i-1]; //下三角
        }
        for(int i=len-2;i>=0;i--){
            tmp *= a[i+1]; //上三角元素在第i行的乘积
            res[i] *= tmp; //上下三角相乘
        }
        return res;
    }
}