我今天接受了采访,被问到这个问题!
编写MS Paint程序.N*N像素区域.给定像素和颜色,将像素中的颜色改变为所需颜色,如果相邻像素具有相同颜色,则也改变它们.
我接近它说我将采取一个*n数组并检查给定的像素并移动到相邻的像素.例如,给定的像素是x,yi首先检查数组中x,y的颜色,然后查找(x + 1,y + 1),(x + 1,y),(x,y + 1) ),(X-1,Y),(X-1,Y-1)....
但是面试官不高兴有人会用更好的算法向我推荐另一种方式......它具有更好的空间和时间复杂度!
Jos*_*hua 15
面试官可能要求进行洪水填充,而这种方法无法做到这么简单.
如果这是泛洪填充,则对角线不计为相邻.
最简单的泛洪填充是对阵列上每个相邻像素的递归调用.在大型网格上使用简单方法很可能会耗尽堆栈.
正确的方法是将起始位置入队,然后出列,检查像素颜色是否仍然是源颜色,并在您前进时扫描左右填充,并将所有像素排列在上方和下方.继续,直到队列耗尽.