Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

矩阵置零 #26

Open
louzhedong opened this issue Jun 5, 2018 · 0 comments
Open

矩阵置零 #26

louzhedong opened this issue Jun 5, 2018 · 0 comments

Comments

@louzhedong
Copy link
Owner

题目

出处: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;
    }
  }
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant