在深信服组期间学习了C++的使用方法,就打算通过刷Leetcode来提高自己的算法能力以及对C++的掌握能力
把空间复杂度看成时间复杂度可把人折磨坏了
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
12Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
1 | Input: |
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 | class Solution { |
我的思路
- 把空间复杂度看成时间复杂度,然后想了很久,结果还是两个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
29class 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,确实看不出来为什么比我快,口亨