<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0238. 除自身以外數組的乘積 ## 題目地址(238. 除自身以外數組的乘積) <https://leetcode-cn.com/problems/product-of-array-except-self/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個長度為 n 的整數數組 nums,其中 n > 1,返回輸出數組 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積。 示例: 輸入: [1,2,3,4] 輸出: [24,12,8,6] 提示:題目數據保證數組之中任意元素的全部前綴元素和后綴(甚至是整個數組)的乘積都在 32 位整數范圍內。 說明: 請不要使用除法,且在 O(n) 時間復雜度內完成此題。 進階: 你可以在常數空間復雜度內完成這個題目嗎?( 出于對空間復雜度分析的目的,輸出數組不被視為額外空間。) ``` ``` ## 前置知識 - 數組 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題的意思是給定一個數組,返回一個新的數組,這個數組每一項都是其他項的乘積。 符合直覺的思路是兩層循環,時間復雜度是O(n^2),但是題目要求`Please solve it without division and in O(n)`。 因此我們需要換一種思路,由于輸出的每一項都需要用到別的元素,因此一次遍歷是絕對不行的。 考慮我們先進行一次遍歷, 然后維護一個數組,第i項代表前i個元素(不包括i)的乘積。 然后我們反向遍歷一次,然后維護另一個數組,同樣是第i項代表前i個元素(不包括i)的乘積。 ![](https://img.kancloud.cn/76/2b/762b2ae7e46846fb7007091eea31b40b_829x441.jpg) 有意思的是第一個數組和第二個數組的反轉(reverse)做乘法(有點像向量運算)就是我們想要的運算。 其實我們進一步觀察,我們不需要真的創建第二個數組(第二個數組只是做中間運算使用),而是直接修改第一個數組即可。 ## 關鍵點解析 - 兩次遍歷, 一次正向,一次反向。 - 維護一個數組,第i項代表前i個元素(不包括i)的乘積 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} nums * @return {number[]} */</span> <span class="hljs-keyword">var</span> productExceptSelf = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">const</span> ret = []; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>, temp = <span class="hljs-params">1</span>; i < nums.length; i++) { ret[i] = temp; temp *= nums[i]; } <span class="hljs-title">// 此時ret[i]存放的是前i個元素相乘的結果(不包含第i個)</span> <span class="hljs-title">// 如果沒有上面的循環的話,</span> <span class="hljs-title">// ret經過下面的循環會變成ret[i]存放的是后i個元素相乘的結果(不包含第i個)</span> <span class="hljs-title">// 我們的目標是ret[i]存放的所有數字相乘的結果(不包含第i個)</span> <span class="hljs-title">// 因此我們只需要對于上述的循環產生的ret[i]基礎上運算即可</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = nums.length - <span class="hljs-params">1</span>, temp = <span class="hljs-params">1</span>; i >= <span class="hljs-params">0</span>; i--) { ret[i] *= temp; temp *= nums[i]; } <span class="hljs-keyword">return</span> ret; }; ``` ``` ***復雜度分析*** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) 更多題解可以訪問我的LeetCode題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經30K star啦。 大家也可以關注我的公眾號《力扣加加》獲取更多更新鮮的LeetCode題解
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看