前言
掘金团队号上线，助你 Offer 临门！ 点击 查看详情
题目描述
有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。
方法：（DFS深度优先搜索）
思路：使用递归，递归的结束条件是关键，核心思路是考虑全面边界条件，当上下左右任意一个点超出边界时，或者坐标对应的点和初始坐标对应的颜色不同则返回。
// 解决本题的核心思路是考虑全面边界条件，当上下左右的点超出边界的时候，或者 // 坐标对应的点 和初始坐标对应的颜色不同则返回。 var floodFill = function (image, sr, sc, newColor) { // 记录image的长度 相当于二维矩阵由多少行 let m = image.length; // 记录二维矩阵由多少列 let n = image[0].length; // 记录起始点的颜色值 let orignalColor = image[sr][sc]; // 如果起始点的颜色等于新的颜色，则直接返回二位矩阵 if(image[sr][sc] == newColor) { return image; } // 开始染色的函数 const fill = (i,j) => { if(i < 0 || j < 0 || i == m || j == n ||image[i][j] != orignalColor) { return; } image[i][j] = newColor; // 起始点上边的点 fill(i-1,j); // 起始点下边的点 fill(i+1,j); // 起始点左边的点 fill(i,j-1); // 起始点右边的点 fill(i,j+1); } // 调用函数 fill(sr,sc); return image; };
伪代码
function imageFill(image,sr,sc,newColor): // 记录image的长度，相当于二维矩阵的长度 m ← image.length; // 记录二维矩阵列的长度 n ← image[0].length; // 记录起始点的颜色值 orignalColor ← image[sr][sc]; // 如果起始点的颜色和newColor的值相同，直接返回二维矩阵image if image[sr][sc] == newColor: return image; // 图像渲染的函数 function fill(i,j): // 递归的结束条件：如果坐标出界或者目标元素的像素值和起始点颜色值不同则返回。 if (i < 0 || j < 0 || i == m || j == n ||image[i][j] != orignalColor)： return； // 将第i行第j列的值修改为新的像素值 image[i][j] = newColor; // 分别将上下左右四个点的坐标代入递归函数 fill(i-1,j); fill(i+1,j); fill(i,j-1); fill(i,j+1); // 调用图像渲染函数 fill(sr,sc); // 返回渲染后的图像 return image;
算法复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)