谷狗电面背靠背（求大米！！！）

Tazdingo 发表于 2019/02/08 13:01:26


为啥按sum排序就能保证找到距离最短的？而且这样复杂度也没bfs好啊

想了下，不能保证曼哈顿距离最短。BFS的时间复杂度要O(n^3)了，n为边长。我在想是否有更快的算法呢？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

sanmi0814 发表于 2019-2-8 23:29
sum方法还是O(N**2)，不用排序，只要记录一个最小就好

先把所有X点挑出来；所有Y点挑出来

设N是我们矩阵的边长，worst case X Y 的集合size大小都是 N^2 , loop的复杂度就是N^4
但是做BFS就只有N^2

我面试的第一题和lz一样
第一题就bfs 最差是matrix的size，space也是最差matrix的size
如果存x和y的话 最差时间复杂度（matrix一半x一半y）会到matrix size的平方吧。

376992718 发表于 2019-2-10 06:46
设N是我们矩阵的边长，worst case X Y 的集合size大小都是 N^2 , loop的复杂度就是N^4
但是做BFS就只有N ...

明白了！感谢回复！！！！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

YJacob 发表于 2019-2-10 09:53
假如最差情况有N**2级别的X点，每个X做bfs需要的时间也是N**2级别，那最差情况不也是N**4吗？这里我没搞 ...

不会啊 从所有的X都放进queue里同时开始bfs 每个点最多visit一次 复杂度肯定是矩阵大小啊

Tazdingo 发表于 2019-2-10 11:36
不会啊 从所有的X都放进queue里同时开始bfs 每个点最多visit一次 复杂度肯定是矩阵大小啊

同时开始bfs怎么理解呀

YJacob 发表于 2019-2-11 00:05
同时开始bfs怎么理解呀

就是一开始把所有的X点都放进queue里啊，然后用queue大小来确定下一层循环次数，已经从别的X到达了的点就不去了，然后第一个扩散到Y的就是结果了。

Tazdingo 发表于 2019-2-11 10:57
就是一开始把所有的X点都放进queue里啊，然后用queue大小来确定下一层循环次数，已经从别的X到达了的点就 ...

噢噢明白啦！ 多谢多谢！！