九章算法 | 微软面试题：数组除了自身的乘积

给定n个整数的数组nums，其中n> 1，返回一个数组输出，使得output [i]等于nums的所有除了nums [i]的元素的乘积。

在线评测地址: LintCode 领扣

样例

样例1

        输入: [1,2,3,4]
输出: [24,12,8,6]
解释:
2*3*4=24
1*3*4=12
1*2*4=8
1*2*3=6
      

样例2

        输入: [2,3,8]
输出: [24,16,6]
解释:
3*8=24
2*8=16
2*3=6
      

【题解】

方法1: 求出整个数组和积 然后对与每个数的答案，就是这个数组的积除以这个数

方法2: 采用前缀和数组的思路我们用一个数组记录nums0 nums1 ...numsi-1,再记录numsi+1 ... * numsn-1，将这两个数相乘即可获得resi。

        public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 1; i < n; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
}
      

更多题解参见： 九章算法