[閒聊] 每日leetcode 75 - Day4

[yam276 (史萊哲林的優等生)]

238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/


題意：

輸出陣列要是輸入陣列所有左與右元素的乘積 不包含自己

空間複雜度要 O(n) 而且不能用除法


思路：

題目的限制等於禁止用兩層 for

但可以用兩次 for

所以第一次先建全部為 1 的輸出陣列

讓他們從左往右乘

會跟滾雪球一樣越滾越大


再從右往左乘

但此時輸出陣列已經被動過了

所以要一個 temp 來充當中介


Code:

impl Solution {
    pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
        let mut ans = vec![1; nums.len()];

        for i in 1..nums.len() {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        let mut right = 1;
        for i in (0..nums.len()).rev() {
            ans[i] *= right;
            right *= nums[i];
        }
        ans
    }
}


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.97 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1749033477.A.CAD.html