挑戰賽進行到一半,第三週的第一題就開始是 Medium:238. Product of Array Except Self

題目給定一個陣列,對每個 element i 計算除了他之外的其他 element 乘積。可能是因為題目直觀不難,另外加上了需要O(N) 以及不能使用除法的限制。

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

那如果還是要用暴力法呢,結果就 TLE 了 xD

vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans(nums.size(), 1);
        for(int i=0; i<nums.size(); i++){
            for(int j=0; j<nums.size(); j++){
                if(i==j) continue;
                else ans[i] *= nums[j];
            }
        }
        return ans;
    }

借用官方說明圖解,可以發現其實就是自己左邊乘上右邊(好像有點像廢話😆

所以我們可以準備兩個陣列,分別存從左邊乘過來/右邊乘過來的結果

這樣每個 element i 就是相對應的左邊*右邊的乘積囉。

vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> ans(nums.size());
    vector<int> l(nums.size(),1);
    vector<int> r(nums.size(),1);
    
    for(int i=1; i<nums.size(); i++){
        l[i] = l[i-1] * nums[i-1];
    }
    
    for(int i=(int)nums.size()-2; i>=0; i--){
        r[i] = r[i+1] * nums[i+1];
    }
    
    for(int i=0; i<nums.size(); i++)
        ans[i] = l[i] * r[i];

    return ans;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料