<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之旅 廣告
                # 0073. 矩陣置零 ## 題目地址(73. 矩陣置零) <https://leetcode-cn.com/problems/set-matrix-zeroes/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個 m x n 的矩陣,如果一個元素為 0,則將其所在行和列的所有元素都設為 0。請使用原地算法。 示例 1: 輸入: [ [1,1,1], [1,0,1], [1,1,1] ] 輸出: [ [1,0,1], [0,0,0], [1,0,1] ] 示例 2: 輸入: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] 輸出: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ] 進階: 一個直接的解決方案是使用 O(mn) 的額外空間,但這并不是一個好的解決方案。 一個簡單的改進方案是使用 O(m + n) 的額外空間,但這仍然不是最好的解決方案。 你能想出一個常數空間的解決方案嗎? ``` ``` ## 前置知識 - 狀態壓縮 ## 公司 - 阿里 - 百度 - 字節 ## 思路 符合直覺的想法是,使用一個 m + n 的數組來表示每一行每一列是否”全部是 0“, 先遍歷一遍去構建這樣的 m + n 數組,然后根據這個 m + n 數組去修改 matrix 即可。 ![](https://img.kancloud.cn/00/a3/00a3a8ba77d6553d3a2e7aebc77696a2_604x437.jpg) 這樣的時間復雜度 O(m \* n), 空間復雜度 O(m + n). 代碼如下: ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> setZeroes = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">matrix</span>) </span>{ <span class="hljs-keyword">if</span> (matrix.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> matrix; <span class="hljs-keyword">const</span> m = matrix.length; <span class="hljs-keyword">const</span> n = matrix[<span class="hljs-params">0</span>].length; <span class="hljs-keyword">const</span> zeroes = <span class="hljs-params">Array</span>(m + n).fill(<span class="hljs-params">false</span>); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < m; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">0</span>; j < n; j++) { <span class="hljs-keyword">const</span> item = matrix[i][j]; <span class="hljs-keyword">if</span> (item === <span class="hljs-params">0</span>) { zeroes[i] = <span class="hljs-params">true</span>; zeroes[m + j] = <span class="hljs-params">true</span>; } } } <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < m; i++) { <span class="hljs-keyword">if</span> (zeroes[i]) { matrix[i] = <span class="hljs-params">Array</span>(n).fill(<span class="hljs-params">0</span>); } } <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < n; i++) { <span class="hljs-keyword">if</span> (zeroes[m + i]) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">0</span>; j < m; j++) { matrix[j][i] = <span class="hljs-params">0</span>; } } } <span class="hljs-keyword">return</span> matrix; }; ``` ``` 但是這道題目還有一個 follow up, 要求使用 O(1)的時間復雜度。因此上述的方法就不行了。 但是我們要怎么去存取這些信息(哪一行哪一列應該全部為 0)呢? 一種思路是使用第一行第一列的數據來代替上述的 zeros 數組。 這樣我們就不必借助額外的存儲空間,空間復雜度自然就是 O(1)了。 由于我們不能先操作第一行和第一列, 因此我們需要記錄下”第一行和第一列是否全是 0“這樣的一個數據,最后根據這個信息去 修改第一行和第一列。 具體步驟如下: - 記錄下”第一行和第一列是否全是 0“這樣的一個數據 - 遍歷除了第一行和第一列之外的所有的數據,如果是 0,那就更新第一行第一列中對應的元素為 0> 你可以把第一行第一列看成我們上面那種解法使用的 m + n 數組。 - 根據第一行第一列的數據,更新 matrix - 最后根據我們最開始記錄的”第一行和第一列是否全是 0“去更新第一行和第一列即可 ![](https://img.kancloud.cn/2b/14/2b1474c18d101d3d1824c790f0a7be1e_730x321.jpg) ## 關鍵點 - 使用第一行和第一列來替代我們 m + n 數組 - 先記錄下”第一行和第一列是否全是 0“這樣的一個數據,否則會因為后續對第一行第一列的更新造成數據丟失 - 最后更新第一行第一列 ## 代碼 - 語言支持:JS,Python3 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=73 lang=javascript * * [73] Set Matrix Zeroes */</span> <span class="hljs-title">/** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */</span> <span class="hljs-keyword">var</span> setZeroes = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">matrix</span>) </span>{ <span class="hljs-keyword">if</span> (matrix.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> matrix; <span class="hljs-keyword">const</span> m = matrix.length; <span class="hljs-keyword">const</span> n = matrix[<span class="hljs-params">0</span>].length; <span class="hljs-title">// 時間復雜度 O(m * n), 空間復雜度 O(1)</span> <span class="hljs-keyword">let</span> firstRow = <span class="hljs-params">false</span>; <span class="hljs-title">// 第一行是否應該全部為0</span> <span class="hljs-keyword">let</span> firstCol = <span class="hljs-params">false</span>; <span class="hljs-title">// 第一列是否應該全部為0</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < m; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">0</span>; j < n; j++) { <span class="hljs-keyword">const</span> item = matrix[i][j]; <span class="hljs-keyword">if</span> (item === <span class="hljs-params">0</span>) { <span class="hljs-keyword">if</span> (i === <span class="hljs-params">0</span>) { firstRow = <span class="hljs-params">true</span>; } <span class="hljs-keyword">if</span> (j === <span class="hljs-params">0</span>) { firstCol = <span class="hljs-params">true</span>; } matrix[<span class="hljs-params">0</span>][j] = <span class="hljs-params">0</span>; matrix[i][<span class="hljs-params">0</span>] = <span class="hljs-params">0</span>; } } } <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i < m; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">1</span>; j < n; j++) { <span class="hljs-keyword">const</span> item = matrix[i][j]; <span class="hljs-keyword">if</span> (matrix[<span class="hljs-params">0</span>][j] == <span class="hljs-params">0</span> || matrix[i][<span class="hljs-params">0</span>] == <span class="hljs-params">0</span>) { matrix[i][j] = <span class="hljs-params">0</span>; } } } <span class="hljs-title">// 最后處理第一行和第一列</span> <span class="hljs-keyword">if</span> (firstRow) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < n; i++) { matrix[<span class="hljs-params">0</span>][i] = <span class="hljs-params">0</span>; } } <span class="hljs-keyword">if</span> (firstCol) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < m; i++) { matrix[i][<span class="hljs-params">0</span>] = <span class="hljs-params">0</span>; } } <span class="hljs-keyword">return</span> matrix; }; ``` ``` Python3 Code: 直接修改第一行和第一列為 0 的解法: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">setZeroes</span><span class="hljs-params">(self, matrix: List[List[int]])</span> -> <span class="hljs-keyword">None</span>:</span> <span class="hljs-string">""" Do not return anything, modify matrix in-place instead. """</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">setRowZeros</span><span class="hljs-params">(matrix: List[List[int]], i:int)</span> -> <span class="hljs-keyword">None</span>:</span> C = len(matrix[<span class="hljs-params">0</span>]) matrix[i] = [<span class="hljs-params">0</span>] * C <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">setColZeros</span><span class="hljs-params">(matrix: List[List[int]], j:int)</span> -> <span class="hljs-keyword">None</span>:</span> R = len(matrix) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(R): matrix[i][j] = <span class="hljs-params">0</span> isCol = <span class="hljs-keyword">False</span> R = len(matrix) C = len(matrix[<span class="hljs-params">0</span>]) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(R): <span class="hljs-keyword">if</span> matrix[i][<span class="hljs-params">0</span>] == <span class="hljs-params">0</span>: isCol = <span class="hljs-keyword">True</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, C): <span class="hljs-keyword">if</span> matrix[i][j] == <span class="hljs-params">0</span>: matrix[i][<span class="hljs-params">0</span>] = <span class="hljs-params">0</span> matrix[<span class="hljs-params">0</span>][j] = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, C): <span class="hljs-keyword">if</span> matrix[<span class="hljs-params">0</span>][j] == <span class="hljs-params">0</span>: setColZeros(matrix, j) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(R): <span class="hljs-keyword">if</span> matrix[i][<span class="hljs-params">0</span>] == <span class="hljs-params">0</span>: setRowZeros(matrix, i) <span class="hljs-keyword">if</span> isCol: setColZeros(matrix, <span class="hljs-params">0</span>) ``` ``` 另一種方法是用一個特殊符合標記需要改變的結果,只要這個特殊標記不在我們的題目數據范圍(0 和 1)即可,這里用 None。 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">setZeroes</span><span class="hljs-params">(self, matrix: List[List[int]])</span> -> <span class="hljs-keyword">None</span>:</span> <span class="hljs-string">""" 這題要解決的問題是,必須有個地方記錄判斷結果,但又不能影響下一步的判斷條件; 直接改為0的話,會影響下一步的判斷條件; 因此,有一種思路是先改為None,最后再將None改為0; 從條件上看,如果可以將第一行、第二行作為記錄空間,那么,用None應該也不算違背題目條件; """</span> rows = len(matrix) cols = len(matrix[<span class="hljs-params">0</span>]) <span class="hljs-title"># 遍歷矩陣,用None記錄要改的地方,注意如果是0則要保留,否則會影響下一步判斷</span> <span class="hljs-keyword">for</span> r <span class="hljs-keyword">in</span> range(rows): <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> range(cols): <span class="hljs-keyword">if</span> matrix[r][c] <span class="hljs-keyword">is</span> <span class="hljs-keyword">not</span> <span class="hljs-keyword">None</span> <span class="hljs-keyword">and</span> matrix[r][c] == <span class="hljs-params">0</span>: <span class="hljs-title"># 改值</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(rows): matrix[i][c] = <span class="hljs-keyword">None</span> <span class="hljs-keyword">if</span> matrix[i][c] != <span class="hljs-params">0</span> <span class="hljs-keyword">else</span> <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(cols): matrix[r][j] = <span class="hljs-keyword">None</span> <span class="hljs-keyword">if</span> matrix[r][j] != <span class="hljs-params">0</span> <span class="hljs-keyword">else</span> <span class="hljs-params">0</span> <span class="hljs-title"># 再次遍歷,將None改為0</span> <span class="hljs-keyword">for</span> r <span class="hljs-keyword">in</span> range(rows): <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> range(cols): <span class="hljs-keyword">if</span> matrix[r][c] <span class="hljs-keyword">is</span> <span class="hljs-keyword">None</span>: matrix[r][c] = <span class="hljs-params">0</span> ``` ``` **復雜度分析** - 時間復雜度:O(M?N)O(M \* N)O(M?N) - 空間復雜度:O(1)O(1)O(1) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg) ## 擴展 為什么選擇第一行第一列,選擇其他行和列可以么?為什么?
                  <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>

                              哎呀哎呀视频在线观看