未分類

Product of Array Except Self

Array, Go, LeetCode

Product of Array Except Self

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.)

提示 解題應用
Array Array/Slice

Default:

1
2
3
func productExceptSelf(nums []int) []int {
}

解答思路:

要回傳一個與原數列相同長度的陣列，且其每個元素是不包含原數列位置所有其它值的乘積，如果沒有其它限制的話就只要先全數遍歷一次數列得到所有元素的乘積，接著只要再分別將所有元素的乘積對每個元素的值相除，並放入對應的陣列位置就搞定，不過當然底下有要求要在時間複雜度為O(n)，空間複雜度為O(1)(不包含要回傳的陣列空間)，且最重要的是不能用”/“這個運算子，所以只能以其它方式來處理，仔細想想會發現如果要不包含原數列位置的乘積，那就是在”該位置之前所有元素的乘積”乘上”該位置之後所有元素的乘積”，而”該位置之前所有元素的乘積”其實就是紀錄開頭到前一個位置的所有元素乘積，反之”該位置之後所有元素的乘積”就是紀錄結尾到後一個位置的所有元素乘積，所以只要遍歷兩次數列，第一次先從頭開始遍歷，並在結果陣列中的每個位置上紀錄開頭到前一個位置的所有元素乘積，接著第二次則是從結尾開始遍歷，將”該位置之後所有元素的乘積”的暫存值與結果陣列其位置上所儲存的”該位置之前所有元素的乘積”相乘就會是目標要求每個元素的結果。

程式碼解說:

一開始先初始化一個與原數列相同長度的結果陣列，接下來要在陣列的每個位置上紀錄”該位置之前所有元素的乘積”，而這邊實際的做法是每當從數列取出一個值，便將該值與該值所對應結果陣列位置的值相乘作為下一個在結果陣列位置上的值，一直取到數列的倒數第二個值為止(因為結果陣列最後一個值是數列開頭到倒數第二個元素之間的相乘)，而記得要將結果陣列的第一個元素初始化為1，才不後導致後續的結果全數為0

1
2
3
4
5
output := make([]int, len(nums))
output[0] = 1
for i, v := range nums[:len(nums)-1] {
	output[i+1] = output[i] * v
}

接著則是從結尾開始遍歷並初始化一暫存值為1，與上述同理只取到數列的第二個值為止，”該位置之後所有元素的乘積”與”該位置之前所有元素的乘積”相乘就會是目標要求每個元素的結果，這邊實際的做法是暫存值紀錄結尾到取出元素之間的相乘，而前一個在結果陣列位置上的值就是其值(前一個在結果陣列位置上的值)與暫存值相乘

1
2
3
4
5
6
7
8
tmp := 1
i := len(nums) - 1
for i > 0 {
	tmp *= nums[i]
	output[i-1] *= tmp
	i--
}
return output

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func productExceptSelf(nums []int) []int {
	output := make([]int, len(nums))
	output[0] = 1
	for i, v := range nums[:len(nums)-1] {
		output[i+1] = output[i] * v
	}
	tmp := 1
	i := len(nums) - 1
	for i > 0 {
		tmp *= nums[i]
		output[i-1] *= tmp
		i--
	}
	return output
}

總結:

要回傳一個與原數列相同長度的陣列，其每個元素是不包含原數列位置所有其它值的乘積，且時間複雜度為O(n)，空間複雜度為O(1)(不包含要回傳的陣列空間)，最重要的是不能用”/“這個運算子，而其做法總共要遍歷兩次數列，第一次先從頭開始遍歷，並在結果陣列中的每個位置上紀錄開頭到前一個位置的所有元素乘積，接著第二次則是從結尾開始遍歷，將”該位置之後所有元素的乘積”的暫存值與結果陣列其位置上所儲存的”該位置之前所有元素的乘積”相乘就會是目標要求每個元素的結果。

分享到