LeetCode OJ 238. Product of Array Except Self 解題報告

238. Product of Array Except Self

My SubmissionsQuestionTotal Accepted:36393Total Submissions:87262Difficulty:Medium

Given an array ofnintegers wheren> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[i].

Solve itwithout divisionand in O(n).

For example, given[1,2,3,4], return[24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output arraydoes notcount as extra space for the purpose of space complexity analysis.)

Subscribeto see which companies asked this question

Show Tags Show Similar Problems Have you met this question in a real interview? Yes No

給出一個數組，要求計算一個新數組，數組裡所有的元素都是除了自己以外的元素乘積。並且要求不許用除法。

《編程之美》上的一道原題。創建兩個輔助數組，一個保存所有左邊元素乘積的結果。一個保存所有右邊元素乘積的結果。借助這兩個數組，一次遍歷就可以得到結果。

我的AC代碼

public class ProductofArrayExceptSelf {

	public static void main(String[] args) {
		int[] a = { 1, 2, 3, 4 };
		System.out.print(Arrays.toString((productExceptSelf(a))));
	}

	public static int[] productExceptSelf(int[] nums) {
		int len = nums.length;
		int[] r = new int[len];

		int[] left = new int[len];
		int[] right = new int[len];
		left[0] = nums[0];
		for (int i = 1; i < len; i++) {
			left[i] = left[i - 1] * nums[i];
		}
		right[len - 1] = nums[len - 1];
		for (int i = len - 2; i >= 0; i--) {
			right[i] = right[i + 1] * nums[i];
		}

		r[0] = right[1];
		r[len - 1] = left[len - 2];
		for (int i = 1; i < len - 1; i++) {
			r[i] = left[i - 1] * right[i + 1];
		}
		return r;
	}
}