set matrix zeroes Leetcode 73 Set Matrix Zeroes－IT工程師數位筆記本

文章出處

Given amxnmatrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?

A straight forward solution using O(mn) space is probably a bad idea.

A simple improvement uses O(m+n) space, but still not the best solution.

Could you devise a constant space solution?

找出矩陣中的0點，并將所在行列都置0

具體要求為使用較小的空間，開始m+n的做法

class Solution {public:    void setZeroes(vector>& matrix) {        vector x;        for(int i=0;i在discuss中看到的O(1)做法，將是否有0存在每一行每一列的第一個位置，因為行列會交叉，因而會當左上角為0時會不知道到底是行還是列，
所以引入col0記錄，col0為0表示是第一列產生的0
void setZeroes(vector > &matrix) {    int col0 = 1, rows = matrix.size(), cols = matrix[0].size();    for (int i = 0; i < rows; i++) {        if (matrix[i][0] == 0) col0 = 0;        for (int j = 1; j < cols; j++)            if (matrix[i][j] == 0)                matrix[i][0] = matrix[0][j] = 0;    }    for (int i = rows - 1; i >= 0; i--) {        for (int j = cols - 1; j >= 1; j--)            if (matrix[i][0] == 0 || matrix[0][j] == 0)                matrix[i][j] = 0;        if (col0 == 0) matrix[i][0] = 0;    }}();i++)>

就愛閱讀www.92to.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20161116/53965.html

文章列表