LeetCode / 3 min read
LeetCode - 238. Product of Array Except Self
LeetCode238
On this page
題目: 53. Product of Array Except Self
給一陣列，逐個取其左、右方所有數字之乘積，但不包含自身；並返回此陣列。
解題思路
Iterate時，同時記錄prefix(左方乘積之值)、postfix(右方乘積之值)，並把值計算於對應之slice。
單一次的iterate時，同時處理nums[i]之prefix與nums[length - i - 1]之postfix。
Code
Java:
Runtime 3 ms(21.87%), Memory 50.5 MB(70.38%)
class Solution { public int[] productExceptSelf(int[] nums) { int length = nums.length; int prefix = 1, postfix = 1; int[] answer = new int[length]; Arrays.fill(answer, 1); for(int i=0; i<length; i++){ // multiple prefix answer[i] *= prefix; prefix *= nums[i]; answer[length - i - 1] *= postfix; postfix *= nums[length - i - 1]; } return answer; }}Python3:
Runtime 246 ms(58.82%),Memory 21.3 MB(47.26%)
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: lengthOfInput = len(nums) answer = [1] * lengthOfInput prefix = 1 postfix = 1 for i in range(lengthOfInput): answer[i] *= prefix prefix *= nums[i] answer[lengthOfInput - i - 1] *= postfix postfix *= nums[lengthOfInput - i - 1] return answerC#:
Runtime 180 ms(47.39%), Memory 53.9 MB(61.68%)
public class Solution { public int[] ProductExceptSelf(int[] nums) { int length = nums.Length; int[] answer = new int[length]; Array.Fill(answer, 1); int prefix = 1, postfix = 1; for(int i = 0; i < length; i++){ answer[i] *= prefix; prefix *= nums[i]; answer[length - i - 1] *= postfix; postfix *= nums[length - i - 1]; } return answer; }}Golang:
Runtime 27 ms(64.43%), Memory 7.6 MB(39.3%)
func productExceptSelf(nums []int) []int { var length int = len(nums) answer := make([]int, length) for i := range answer { answer[i] = 1 } var prefix int = 1 var postfix int = 1 for i := 0; i < length; i = i+1 { answer[i] *= prefix prefix *= nums[i] answer[length - i - 1] *= postfix postfix *= nums[length - i - 1] } return answer}C++:
Runtime 16 ms(98.12%), Memory 24.1 MB(54.53%)
class Solution {public: vector<int> productExceptSelf(vector<int>& nums) { int length = nums.size(); int prefix = 1, postfix = 1; vector<int> answer(length, 1); for(int i=0; i<length; i++){ answer[i] *= prefix; prefix *= nums[i]; answer[length - i - 1] *= postfix; postfix *= nums[length -i -1]; } return answer; }};