LeetCode - 238. Product of Array Except Self

題目: 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%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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 answer
                

C#:

Runtime 180 ms(47.39%), Memory 53.9 MB(61.68%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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;
    }
};