iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

0
Software Development

LeetCode刷題日記系列 第 26

【Day 26】#238 - Product of Array Except Self

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

Example:

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

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

解析

此題給予一個陣列字串num,要求回傳一陣列,該陣列中的每個元素必須是原陣列中其他元素相乘的乘積,並且不能用除法來解。難度為Medium。

可宣告兩個陣列LR,L陣列的第一個元素為1,其餘每個元素皆為L陣列的前一個元素與nums陣列中相對位置的前一個元素之乘積,即L[i] = L[i−1] * nums[i−1]
R陣列的最後一個元素為1,其餘每個元素皆為R陣列的後一個元素與nums陣列中相對位置的後一個元素之乘積,即R[i] = R[i+1] * nums[i+1]
最後將兩陣列相對位置的元素一一相乘並儲存到新陣列,所得到的新陣列即為所求。

Follow up要求空間複雜度為O(1),可透過先前宣告的L或R陣列,將該陣列中的元素逐次乘以一變數,該變數初始值為1,之後該變數逐次乘上nums陣列中相對位置的值,因為題目說回傳的陣列其空間複雜度不計,則最後得到的陣列即為所求。

解法

時間複雜度:O(N)
空間複雜度:O(N)

class Solution {
    public int[] productExceptSelf(int[] nums) {

        int length = nums.length;
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];

        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }
        return answer;
    }
}

Follow up解法

時間複雜度:O(N)
空間複雜度:O(1)

class Solution {
    public int[] productExceptSelf(int[] nums) {

        int length = nums.length;
        int[] answer = new int[length];
        
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }
        
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            answer[i] = answer[i] * R;
            R *= nums[i];
        }
        return answer;
    }
}

備註


希望透過記錄解題的過程,可以對於資料結構及演算法等有更深一層的想法。
如有需訂正的地方歡迎告知,若有更好的解法也歡迎留言,謝謝。


上一篇
【Day 25】#3 - Longest Substring Without Repeating Characters
下一篇
【Day 27】#1282 - Group the People Given the Group Size They Belong To
系列文
LeetCode刷題日記30

尚未有邦友留言

立即登入留言