【简单】不包含本位置值的累乘数组－Java：进阶问题

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.ArrayAndMatrix; import java.util.Arrays; /** * 不包含本位置值的累乘数组 * * 【题目】 * 给定一个整型数组arr，返回不包含本位置值的累乘数组。 * 例如，arr=[2,3,1,4]，返回[12,8,24,6]，即除自己外，其他位置上的累乘。 * * 【要求】 * 1.时间复杂度为O(N)。 * 2.除需要返回的结果数组外，额外空间复杂度为O(1)。 * * 【进阶题目】 * 对时间和空间复杂度的要求不变，而且不可以使用除法。 * * 【难度】 * 简单 * * 【解答】 * 不能使用除法的情况下，可以用以下方法实现进阶问题： * 1.生成两个长度和arr一样的新数组lr[]和rl[]。lr[]表示从左到右的累乘（即lr[i]=arr[0..i]）的累乘。rl表示从右到左的 * 累乘(即rl[i]=arr[i..N-1])的累乘。 * 2.一个位置上除去自己值的累乘，就是自己左边的累乘再乘以自己右边的累乘，即res[i]=lr[i-1]*rl[i+1]。 * 3.最左的位置和最右位置的累乘比较特殊，即res[0]=rl[1]，res[N-1]=lr[N-2]。 * 以上思路虽然可以得到结果res，但是除res之外，又使用了两个额外数组，怎么省掉这两个额外数组呢？可以通过res数组复用的方 * 式。也就是说，先把res数组作为辅助计算的数组，然后把res调整成结果数组返回。具体过程请参看如下代码中的product2方法。 * * @author Created by LiveEveryDay */ public class NotContainCurrentCumulativeProductArray2 { public static int[] product2(int[] arr) { if (arr == null || arr.length < 2) { return null; } int[] res = new int[arr.length]; res[0] = arr[0]; for (int i = 1; i < arr.length; i++) { res[i] = res[i - 1] * arr[i]; } int tmp = 1; for (int i = arr.length - 1; i > 0; i--) { res[i] = res[i - 1] * tmp; tmp *= arr[i]; } res[0] = tmp; return res; } public static void main(String[] args) { int[] arr = {-4, 3, -2, 5, -7, 1, 6}; int[] res = product2(arr); System.out.printf("The array is: %s", Arrays.toString(res)); } } // ------ Output ------ /* The array is: [1260, -1680, 2520, -1008, 720, -5040, -840] */