矩阵置零

[louzhedong]

题目

出处：LeetCode 算法第73题

给定一个 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(m**n) 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个常数空间的解决方案吗？

思路

遍历所有的元素，将元素为零的坐标对放入临时数组中，遍历临时数组，置行和列的元素为零。

解答

var setZeroes = function (matrix) {
  if (matrix.lenght == 0) {
    return [];
  }
  var max_i = matrix.length;
  var max_j = matrix[0].length;
  var temp = [];
  for (var i = 0; i < max_i; i++) {
    for (var j = 0; j < max_j; j++) {
      if (matrix[i][j] == 0) {
        temp.push([i, j]);
      }
    }
  }
  for (var x = 0; x < temp.length; x++) {
    var a = temp[x][0];
    var b = temp[x][1];
    for (var i = 0; i < max_i; i++) {
      matrix[i][b] = 0;
    }
    for (var j = 0; j < max_j; j++) {
      matrix[a][j] = 0;
    }
  }
};