关于java:LeetCode238除自身以外数组的乘积

4次阅读

共计 954 个字符，预计需要花费 3 分钟才能阅读完成。

题目形容：给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输入数组 output，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：数组遍历

大略的思路是遍历 2 次数组别离计算前缀乘积和后缀乘积，期间将其相乘，具体处理过程如下：

首先，申明一个和原数组大小雷同的数组用于暂存累成的积；

而后，从前往后遍历数组记录每一个地位的前缀累乘积；

而后，从后往前遍历数组并计算每一个地位的后缀累乘积，并且要和上一次遍历失去的前缀累乘积相乘即可失去相应地位的非本身累乘积。

最初，返回这个暂存数组即为后果。

import java.util.Arrays;

public class LeetCode_238 {public static int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        // 因为是算乘积，先都初始化为 1
        Arrays.fill(temp, 1);
        // 计算前缀和乘积 temp[i] 示意第 i 个数后面所有数的乘积
        for (int i = 1; i < len; i++) {temp[i] = temp[i - 1] * nums[i - 1];
        }
        // 递推求后缀和乘积，同时将后果放到前缀和数组中
        // 从后往前，因为要递推后缀和乘积，开端的初始为 1
        for (int i = len - 1, subfixS = 1; i >= 0; i--) {
            // 以后数的乘积后果等于 前缀和乘后缀和
            temp[i] = temp[i] * subfixS;
            // 更新后缀和
            subfixS *= nums[i];
        }
        return temp;
    }

    public static void main(String[] args) {int[] nums = new int[]{1, 2, 3, 4};
        // 测试用例，冀望输入：[24,12,8,6]
        for (int i : productExceptSelf(nums)) {System.out.print(i + " ");
        }
    }
}