【前端算法】#542.01 找出每个元素到最近的 0 的距离

553 阅读3分钟

给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。

示例 1:
输入:

0 0 0
0 1 0
0 0 0
输出:

0 0 0
0 1 0
0 0 0
示例 2:
输入:

0 0 0
0 1 0
1 1 1
输出:

0 0 0
0 1 0
1 2 1

注意:

  • 给定矩阵的元素个数不超过 10000。
  • 给定矩阵中至少有一个元素是 0。
  • 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

一、创建矩阵

示例:创建一个根据行列,创建数组,并填入数字;

     let col = 3; //列数
     let row = 3; //行数
     let matrix = []; //创建一个数组存储空间
     let num = 1;  //填入的值
     for(let i=0;i<row;i++){
      matrix[i] = [];  //创建三维数组行空间
      for(let j=0;j<col;j++){
       matrix[i][j]=num; //填入数字
       num++; 
      }
     }
  输出:
  [
    [1,2,3],
    [4,5,6],
    [7,8,9],
  ]

解题第一步:

//实参替换形参中不为0的值,保留为0的值
var updateMatrix = function(matrix) {
        let row = matrix.length; //获取矩阵的行数
        let col = matrix[0].length; //获取矩阵的列 
 var temp = [];//创建一个数组存储空间
 for(var i = 0; i < row; i++){
  temp[i] = [];
   for(var j = 0 ; j < col; j++){
        if (matrix[i][j] == 0) {
    temp[i][j] = 0;
        }else{
    temp[i][j] = Number.MAX_SAFE_INTEGER; //值过大防止内存溢出
              }
        }
      }
}

输出

   [
     [0,0,0],
     [0,9007199254740991,0],
     [9007199254740991,9007199254740991,9007199254740991],
     [9007199254740991,9007199254740991,9007199254740991],
   ]

二、根据实参矩阵修改矩阵中为0的值

2.1此时从左至右从上至下,各元素只与上左元素作比较
for (var i = 0; i < row; i++){
 for (var j = 0; j < col; j++){ //此时从左至右从上至下,各元素只与上左元素作比较
  if (j > 0)
   temp[i][j] = Math.min(temp[i][j - 1] + 1, temp[i][j]); //左边元素加1若小则取之
  if (i > 0)
   temp[i][j] = Math.min(temp[i - 1][j] + 1, temp[i][j]); //上边元素加1若小则取之    
  }
}

输出:

      [
         [ 0, 0, 0 ],
         [ 0, 1, 0 ],
         [ 1, 2, 1 ],
         [ 2, 3, 2 ]
      ]
2.2 此时从右至左从下至上,各元素可与下右元素作比较
for (var i = row - 1; i >= 0;i--){
  for (var j = col - 1; j >= 0; j--) { //此时从右至左从下至上,各元素可与下右元素作比较
   if (j < col - 1)
           temp[i][j] = Math.min(temp[i][j + 1] + 1, temp[i][j]); //左边元素加1若小则取之
   if (i < row - 1)
           temp[i][j] = Math.min(temp[i + 1][j] + 1, temp[i][j]); //上边元素加1若小则取之    
  }
 }

输出

          [
               [ 0, 0, 0 ],
               [ 0, 1, 0 ],
               [ 1, 2, 1 ],
               [ 2, 3, 2 ],
         ]

解题代码:

var updateMatrix = function(matrix) {
 //步骤一
 let row = matrix.length; //获取矩阵的行数
 let col = matrix[0].length; //获取矩阵的列
 var temp = []; //创建一个数组存储空间
 for (var i = 0; i < row; i++) {
  temp[i] = [];
  for (var j = 0; j < col; j++) {
   if (matrix[i][j] == 0) {
    temp[i][j] = 0;
   } else {
    /* 值过大防止内存溢出 */
    temp[i][j] = Number.MAX_SAFE_INTEGER;
   }
  }
 }

 //步骤二
 for (var i = 0; i < row; i++) {
  for (var j = 0; j < col; j++) { //此时从左至右从上至下,各元素只与上左元素作比较
   if (j > 0)
    /* 左边元素加1若小则取之 */
    temp[i][j] = Math.min(temp[i][j - 1] + 1, temp[i][j]);
   if (i > 0)
    /* 上边元素加1若小则取之 */
    temp[i][j] = Math.min(temp[i - 1][j] + 1, temp[i][j]);
  }
 }

 //步骤三
 for (var i = row - 1; i >= 0; i--) {
  for (var j = col - 1; j >= 0; j--) { //此时从右至左从下至上,各元素可与下右元素作比较
   if (j < col - 1)
    /* 左边元素加1若小则取之 */
    temp[i][j] = Math.min(temp[i][j + 1] + 1, temp[i][j]);
   if (i < row - 1)
    /* 上边元素加1若小则取之 */
    temp[i][j] = Math.min(temp[i + 1][j] + 1, temp[i][j]);
  }
 }
 return temp;
};

本文使用 mdnice 排版