[LeetCode] 238. Product of Array Except Self

轉自LeetCode

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and 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 array does not count as extra space for the purpose of space complexity analysis.)

<Solution>
因為題目有說不能使用除法，所以不能把整個 array 先乘起來，再除以自己來找到答案

且要求時間複雜度為 O(n)

想法如下

• 總共歷遍兩次，第一次求在自己之前的所有乘積。第二次求在自己之後的所有乘積

• 最後再將兩個乘積再相乘，來得到答案

code如下(參考資料)

	class Solution {
	public:
	vector<int> productExceptSelf(vector<int>& nums) {
	const int len = nums.size();
	//>> calculate all product before self
	vector<int> forward(len, 1);
	for(int i = 1; i < len; i++) {
	forward[i] = forward[i-1] * nums[i-1];
	}
	//>> calculate all product after self
	vector<int> backward(len, 1);
	for(int i = len-2; i >= 0; i--) {
	backward[i] = backward[i+1] * nums[i+1];
	}
	//>> find the ans
	vector<int> ans(len, 1);
	for(int i = 0; i < len; i++) {
	ans[i] = forward[i] * backward[i];
	}
	return ans;
	}
	};

view raw productExceptSelf_1.cpp hosted with ❤ by GitHub

題目也進一步要求，空間複雜度能不能變成 O(1)

所以可以優化一下之前的 code

• 不需要用到兩個 array 來分別存乘積，直接使用 ans 這個 array 來運算

• 在求自己之後的所有乘積時，多用一個變數來幫忙記錄所有乘積

code 如下

	class Solution {
	public:
	vector<int> productExceptSelf(vector<int>& nums) {
	vector<int> ans(nums.size(), 1);
	//>> calculate all the product before self
	for(int i = 1; i < nums.size(); i++) {
	ans[i] = ans[i-1] * nums[i-1];
	}
	//>> calculate all the product after self
	//>> and find the ans
	int afterProduct = 1;
	for(int i = nums.size()-1; i >= 0; i--) {
	ans[i] *= afterProduct;
	afterProduct *= nums[i];
	}
	return ans;
	}
	};

view raw productExceptSelf_2.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public int[] productExceptSelf(int[] nums) {
	int[] ans = new int[nums.length];
	ans[0] = 1;
	//>> calculate the prod of all the elements before self
	for(int i = 1; i < nums.length; i++) {
	ans[i] = ans[i-1] * nums[i-1];
	}
	//>> calculate the prod of all elements except self
	int rightProd = 1;
	for(int i = nums.length-1; i >= 0; i--) {
	ans[i] *= rightProd;
	rightProd *= nums[i];
	}
	return ans;
	}
	}

view raw productExceptSelf.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun productExceptSelf(nums: IntArray): IntArray {
	val ans = IntArray(nums.size) {1}
	//>> product of left
	for(i in 1..nums.lastIndex) {
	ans[i] = nums[i-1] * ans[i-1]
	}
	//>> product of right
	var rightP = 1
	for(i in nums.lastIndex downTo 0) {
	ans[i] *= rightP
	rightP *= nums[i]
	}
	return ans
	}
	}

view raw product_of_array_except_self.kt hosted with ❤ by GitHub