面经给一个cell， 里面有障碍物，求起点到终点的最短路径

FB
给一个cell， 里面有障碍物，求起点到终点的最短路径， follow up 是矩阵很大，但是障碍物很少该怎么办，我答使用List记录位置信息，但是visited 使用list 的话搜索变慢，因此用hashmap。然后他挺满意。 然后分析时间复杂度，使用List表示矩阵的话，首先我们需要知道矩阵的size，需要遍历一遍矩阵，因此增加了额外的消耗，时间效率比使用2d array变慢。但是仍然是O(m*n) 最后他好像感觉还行。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容