Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 238. Product of Array Except Self

發表於 分類於 ， ， Disqus：
這題有點類似 Prefix Sums 的概念，找到陣列中元素自己以外的所有元素的乘績

前言

　　這題有點類似 Prefix Sums 的概念，目標是找到陣列中元素自己以外的所有元素的乘績，放在一個新的陣列裡，雖然有三個迴圈是 O(3n) 的時間複雜度，但常數項通常會被省略，因此該演算法可達 O(n) 的時間複雜度，這裡有 JAVA 和 Python 的寫法。

題目

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.

給定一個整數陣列 nums，回傳一個陣列 answer ，其中 answer[i] 等於所有元素的乘積，除了 nums[i]
保證 nums 陣列中任何的前後綴都適合 32-bit 的整數
你必須寫出一個時間複雜度為 O(n) 的算法且不能使用除法

題目連結：https://leetcode.com/problems/product-of-array-except-self/

題目限制

2 <= nums.length <= 105
30 <= nums[i] <= 30

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

範例

1
2
Input: nums = [1,2,3,4]
Output: [24,12,8,6]

nums [0] ⇒ 把 2、3、4 都乘起來
nums [1] ⇒ 把 1、3、4 都乘起來
(以此類推)
把全部乘完的元素都放在 answer 裡

1
2
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

nums [0] ⇒ 把 1、0、-3、3 都乘起來
nums [1] ⇒ 把 -1、0、-3、3 都乘起來
(以此類推)
把全部乘完的元素都放在 answer 裡

思路&筆記

  • 簡而言之我們要把除了 nums[i] 以外的元素乘起來，並且對每一個 i 做一樣的事情
  • 然後每個索引之前之後的元素都要相乘，就是 自己前面的乘積 * 自己後面的乘積

JAVA 實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] productExceptSelf(int[] nums) {
        
        int left[] = new int[nums.length]; // 前綴乘積
        int right[] = new int[nums.length]; // 後綴乘積
        int answer[] = new int[nums.length];

        left[0] = 1; // 第一個元素設為 1
        right[nums.length-1] = 1; // 陣列最後一個元素設為 1

        for (int i = 1; i < nums.length; i++){
            left[i] = nums[i - 1] * left[i - 1]; // left = [1, 1, 2, 6]
        };

        // 計數器 i 從陣列後面遞減回來
        for (int i = nums.length-2; i >= 0; i--){
            right[i] = nums[i + 1] * right[i + 1]; // right = [24, 12, 4, 1]
        };

        // 把兩個陣列的成績相乘
        for (int i = 0; i < nums.length; i++){
            answer[i] = left[i] * right[i];
        };

        return answer; 
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        left, right, answer = [0] * len(nums), [0] * len(nums), [0] * len(nums)

        left[0] = 1 # 第一個元素設為 1
        right[len(nums)-1] = 1 # 陣列最後一個元素設為 1

        for i in range(1, len(nums)):
            left[i] = nums[i-1] * left[i-1]

        # 計數器 i 從陣列後面遞減回來
        for i in range(len(nums)-2, -1, -1):
            right[i] = nums[i+1] * right[i+1]
        
        # 把兩個陣列的成績相乘
        for i in range(len(nums)):
            answer[i] = left[i] * right[i]
        
        return answer

成績

Language Runtime Memory
Java 2ms 53.43MB
Python 202ms 25.48MB