当前位置：网站首页>LeetCode 練習——劍指 Offer 66. 構建乘積數組

LeetCode 練習——劍指 Offer 66. 構建乘積數組

2022-07-21 12:42:00 【SK_Jaco】

1.題目描述

給定一個數組 A[0,1,…,n-1]，請構建一個數組 B[0,1,…,n-1]，其中 B[i] 的值是數組 A 中除了下標 i 以外的元素的積, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

輸入: [1,2,3,4,5]
輸出: [120,60,40,30,24]

2.解題思路與代碼

2.1 解題思路

題目要求得到數組除當前比特以外的數的乘積，首先想到的是求數組所有數的乘積，然後依次除以當前比特，但是這樣的方法如果遇到 0 就會報錯了。這裏就可以使用前綴和數組的思想，先從左往右遍曆得到當前比特左邊的數的乘積，然後在從右往左遍曆得到當前數右邊所有比特的乘積，最後將當前數左右兩邊的乘積相乘便能够得到最終結果。以 [1, 2, 3, 4, 5] 為例進行詳解
首先我們准備一個數組存放數左邊所有數的乘積。讓第一比特為 1，然後從左往右便利，依次得到當前數左邊的乘積

然後再准備一個數組存放數右邊所有數的乘積。設置數組最後一比特為 1，然後從右往左進行遍曆，依次得到當前數右邊所有數的乘積

最後將兩個數組依次按比特相乘便得到最終的結果

2.2 代碼

class Solution {
    
    public int[] constructArr(int[] a) {
    
        int n = a.length;
        int[] ans = new int[n];
        if (n == 0) {
    
            return ans;
        }
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
    
            left[i] = a[i - 1] * left[i - 1];
        }
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
    
            right[i] = a[i + 1] * right[i + 1];
        }
        for (int i = 0; i < n; i++) {
    
            ans[i] = left[i] * right[i];
        }
        return ans;

    }
}