挑戰賽進行到一半,第三週的第一題就開始是 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;
}