LeetCode - Mảng bội số của mảng gốc

ltd · August 14, 2018, 3:08am

Cho một mảng arr, tạo ra một mảng mới là mảng bội số của arr là ans. Trong đó các phần tử của ans là bội của toàn bộ các phần tử trong arr ngoại trừ arr[i]

Không được dùng phép chia trong bài toán này

Phân tích time and space complexity.

Ví dụ có mảng: [1, 3, 7, 2] thì tạo ra mảng mới
[3*7*2, 1*7*2, 1*3*2, 1*3*7]

Được dùng mọi ngôn ngữ
Cần phân tích giải thuật

Có thể submit thử ở đây để coi giải thuật của mình tốt tới đâu

nxphuc · September 11, 2016, 4:00am

Leetcode
Cho em challenge mọi người là liệu có thể làm trong O(N) time không nhé

ltd · September 11, 2016, 4:05am

Google nhanh quá vậy =))

Để update luôn cái link cho mọi người lên test

nxphuc · September 11, 2016, 4:06am

bài này em làm lâu rồi chứ không GG a ơi :))

ltd · September 11, 2016, 5:48am

Mới submit code trên leetcode, code bằng C++.

17 / 17 test cases passed.
Status: Accepted
Runtime: 52 ms

Submit bằng C


17 / 17 test cases passed.
Status: Accepted
Runtime: 32 ms

Submit bằng Java


17 / 17 test cases passed.
Status: Accepted
Runtime: 2 ms

Thôi chuyển sang code Java cho nó lẹ

Submit bằng Python:


17 / 17 test cases passed.
Status: Accepted
Runtime: 162 ms

AI_Android · September 11, 2016, 7:26am

xét riêng trường hợp số 0
tính tích là P
với mỗi ans[i]=p*arr[i]^(-1);
p/s: O(n) time O(1) extra space

nguyenchiemminhvu · September 11, 2016, 7:24am

17 / 17 test cases passed.
Status: Accepted
Runtime: 59 ms

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res(nums.size());
        
        vector<int> leftToRight(nums.size(), 1);
        vector<int> rightToLeft(nums.size(), 1);
        
        for (int i = 1; i < leftToRight.size(); i++)
            leftToRight[i] = leftToRight[i - 1] * nums[i - 1];
            
        for(int i = rightToLeft.size() - 2; i >= 0; i--)
            rightToLeft[i] = rightToLeft[i + 1] * nums[i + 1];
            
        for(int i = 0; i < nums.size(); i++)
            res[i] = leftToRight[i] * rightToLeft[i];
        
        return res;
    }
};