BoBo老师好，您play-leetcode上的286号问题 Walls and Gates好像代码超时了
来源：6-7 优先队列相关的算法问题 Top K Frequent Elements
Ko1231
2019-06-13
BoBo老师您好，您play-leetcode上的286号问题的代码在leetcode上提交时显示Time Limit Exceeded了，请问老师可以帮忙看一下吗？谢谢?
写回答
1回答
-
liuyubobobo
2019-06-13
感谢提醒。我重新修改了一下，可以参考这里：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0286-Walls-and-Gates/cpp-0286/main.cpp
之前的算法相当于对每一个room进行一次bfs，所以时间复杂度应该是 room_num * m * n 的。
现在优化后的算法，一上来将所有的gate放入队列。之后从gate的位置开始做bfs，到达了某个room，这个距离就是这个room到某个gate的最短距离：）这个算法的时间复杂度是O(m * n )的：）
继续加油！：）
032019-06-15
相似问题