238. Product of Array Except Self (使用 C 語言解題)

238. Product of Array Except Self

Solved

Medium

Topics

Companies

Hint

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.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 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.

 

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

google 翻譯：

給定一個整數數組 nums，傳回一個數組answer，使得 answer[i] 等於 nums 中除 nums[i] 之外的所有元素的乘積。
nums 的任何前綴或後綴的乘積保證適合 32 位元整數。
您必須編寫一個在 O(n) 時間內運作且不使用除法運算的演算法。

想法一：

因為不能用除法，每個數值，要跟其他所有的數值相乘。
最簡單的做法就是跑兩次迴圈...
(如果可以使用除法，做法會是無差別的，用 for 把所有數值都相乘起來。
再跑一次 for 把乘積除以目前用 for 輪到的數值)

寫法一：

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    int i, j;
    int *result = malloc(sizeof(int) * numsSize);
    // （每個數值，都要跟其他所有的數值相乘）
    // 主要的 for 從頭跑到尾
    for(i=0; i<numsSize; i++) {
        result[i] = 1; // 因為要相乘，所以給定初始值 1

        // 第二個 for 除了自己以外，都要相乘
        for(j=0; j<numsSize; j++) {
            if(i != j)
                result[i] *= nums[j];
        }
    }
    *returnSize = numsSize;
    return result;
}

結果一：

這最簡便的寫法看來執行太久了...想辦法增加速度囉...

想法二：

先算好兩組乘積，
第一組乘積從左邊開始往右邊相乘（假設乘積結果為 1(左一) 2(左二) 4(左三) 8(左四)），
第二組乘積從右邊開始往左邊相乘（假設乘積結果為 8(右一) 4(右二) 2(右三) 1(右四)）。
回傳的陣列，從這兩乘積左右各抓取一筆相鄰的數值相乘即可，如：
回傳一 右二 (因為是開頭，所以右二就是答案了)
回傳二 左一 * 右三 (略過自己的位置，左右各取相鄰的一個相乘)
回傳三 左二 * 右四 (略過自己的位置，左右各取相鄰的一個相乘)
回傳四 左三 (因為是結尾，所以左三就是答案了)

寫法二：

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    int i, max;
    int *result = malloc(sizeof(int) * numsSize);
    int *data1 = malloc(sizeof(int) * numsSize); // 第一組乘積
    int *data2 = malloc(sizeof(int) * numsSize); // 第二組乘積

    // 第一組乘積計算，從左邊開始
    for(i=0; i<numsSize; i++) {
        if(i == 0) // 開頭放自己即可
            data1[i] = nums[i];
        else
            data1[i] = data1[i-1] * nums[i];
    }

    // 第二組乘積計算，從右邊開始
    for(i=numsSize-1; i>=0; i--) {
        if(i == numsSize-1) // 結尾放自己即可
            data2[i] = nums[i];
        else
            data2[i] = data2[i+1] * nums[i];
    }

    // 回傳值計算
    for(i=0; i<numsSize; i++) {
        if(i == 0) // 開頭直接抓值
            result[i] = data2[i+1];
        else if(i == numsSize-1) // 結尾直接抓值
            result[i] = data1[i-1];
        else // 中間的要左右各抓一個相鄰的值相乘
            result[i] = data1[i-1] * data2[i+1];
    }
    free(data1);
    free(data2);
    *returnSize = numsSize;
    return result;
}

結果二：

結果雖然差強人意，但至少有成功了。再想優化的方法...

想法三：

把從左邊和從右邊的兩組乘積陣列省略
直接使用要回傳的陣列暫存，也少跑了一次 for

寫法三：

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    int i, product;
    int *result = malloc(sizeof(int) * numsSize);

    // 計算從左邊開始的乘積陣列
    product = 1;
    for(i=0; i<numsSize; i++) {
        result[i] = product;
        product *= nums[i];
    }

    // 計算從右邊開始的乘積陣列，一併直接計算出回傳結果
    product = 1;
    for(i=numsSize-1; i>=0; i--) {
        result[i] *= product;
        product *= nums[i];
    }

    *returnSize = numsSize;
    return result;
}

結果三：

結果不是很好，但可以接受了，也沒有想改的部份了，就這樣吧...