[剑指offer] 其他算法[上]篇-526互联

JZ66 构建乘积数组

/* 暴力 */
public class JZ66_1
{
    public static int[] multiply(int[] A)
    {
        int[] res = new int[A.length];
        Arrays.fill(res, 1);
        for (int i = 0; i < A.length; i++)
        {
            for (int j = 0; j < A.length; j++)
            {
                if (j == i) continue;
                res[i] *= A[j];
            }
        }
        return res;
    }
}

/* 根据 i 分成两部分 */
public class JZ66_2
{
    public static int[] multiply(int[] A)
    {
        int[] res = new int[A.length];
        int temp = 1;
        res[0] = 1;
        for (int i = 1; i < A.length; i++)
            res[i] = res[i - 1] * A[i - 1];
        for (int i = A.length - 1; i >= 0; i--)
        {
            res[i] *= temp;
            temp *= A[i];
        }
        return res;
    }
}