題目描述
給定一個數組A[0,1,…,n-1],請構建一個數組B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1]。不能使用除法。
算法解析： 不能使用除法讓我們構建這樣一個數組B，最直觀的想法莫過于直接使用連乘。但如果每個值都用連乘來生成的話，那么時間復雜度為O(n^2)，但是我們觀察B數組可以發現如下規律B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1];即 B[i]=(A[0]A[1]…A[i-1]) 1 * (A[i+1]*…*A[n-1])也就是說將B數組的生成分為兩部分，第一部分從上到下乘出來，第二部分從下到上乘出來，時間復雜度為O(n)。
代碼如下：
public int[] multiply(int[] A) { if (A == null || A.length <= 0){ return null; } int[] B = new int[A.length]; B[0] = 1; for (int i = 1; i < A.length; i++) { B[i] = B[i - 1] * A[i - 1]; } int temp = 1; for (int i = A.length - 2; i >= 0 ; i--) { temp *= A[i + 1]; B[i] *= temp; } return B; }新聞熱點
疑難解答
