在深信服组期间学习了C++的使用方法，就打算通过刷Leetcode来提高自己的算法能力以及对C++的掌握能力

把空间复杂度看成时间复杂度可把人折磨坏了

Leetcode传送门

Set Matrix Zeroes [Difficulty: Medium]

题目

  • Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
  • Example:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Input: 
    [
      [1,1,1],
      [1,0,1],
      [1,1,1]
    ]
    Output: 
    [
      [1,0,1],
      [0,0,0],
      [1,0,1]
    ]
1
2
3
4
5
6
7
8
9
10
11
12
Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

  • Follow up:

  • 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?
1
2
3
4
5
6
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        
    }
};

我的思路

  • 把空间复杂度看成时间复杂度，然后想了很久，结果还是两个for循环
  • 用了multimap存储0的信息，value为1时key是行数，value为0时key是列数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class Solution {
    public:
        void setZeroes(vector<vector<int>>& matrix) {
            multimap<int,int> Zeros;
            int rowSize = matrix.size();
            int colSize = matrix[0].size();
            for (int i = 0; i<rowSize; ++i)
                for (int j = 0 ;j<colSize; ++j)
                    if (matrix[i][j] == 0){
                        Zeros.insert(pair<int, int>(i, 1));
                        Zeros.insert(pair<int, int>(j, 0));
                    }
            
            multimap<int,int>::iterator iter = Zeros.begin();
            for (; iter!=Zeros.end(); ++iter) {
                if (iter->second == 1) {
                    for (int m =0; m<colSize; ++m) {
                        matrix[iter->first][m] = 0;
                    }
                }
                else {
                    for (int n =0; n<rowSize; ++n) {
                        matrix[n][iter->first] = 0;
                    }
                }
            }
            return;
        } 
    };

参考思路

  • 答案用的是两个list存的信息，而不是multimap，确实看不出来为什么比我快，口亨