Nearest Meeting Cell面试题：能否实现O(logn)时间复杂度解法？

核心结论 #

直接给答案：不存在O(logn)的通用解法。这个问题的图结构决定了必须遍历至少部分路径才能找到公共节点，最坏情况下绕不开O(n)的时间开销。不过我们可以优化O(n)解法的效率，或者通过预处理让查询更快。

先搞懂图的结构 #

题目里每个单元格最多1个出口，所以整个迷宫的图结构很特殊：

• 要么是一条链，最后走到一个没有出口的节点（出边为-1）；
• 要么是一条链最终接入一个环（环里每个节点的出口都指向环内的另一个节点，循环往复）；
• 整个图就是若干个这样的「链+环」或者单独的链组成的。

从任意节点出发的路径是唯一的——要么走到死路，要么进环循环。

为什么O(logn)做不到？ #

要找C1和C2的最近公共可达节点，本质是找两条唯一路径的第一个交点。但路径上的节点编号没有任何有序性或者可二分的性质，没法用二分查找这类O(logn)的操作直接定位交点。最坏情况下，比如C1和C2的路径直到末端才相遇，你必须把两条路径都走完，这时候时间就是O(n)。

最优的实用解法 #

方法1：标记路径法（好写又直观） #

步骤很简单：

1. 从C1出发，顺着出口走，把每个经过的节点标记下来，同时记录每个节点到C1的步数。
2. 再从C2出发走，每碰到一个已经标记过的节点，就算一下它到C2的步数，总步数是「C1到它的步数 + C2到它的步数」，记住总步数最小的那个节点。
3. 如果走完C2的路径都没碰到标记节点，返回-1。

拿示例输入验证：
C1=9的路径：9→8→0→4→13→11→9（进环），标记的节点和步数：9(0)、8(1)、0(2)、4(3)、13(4)、11(5)
C2=2的路径：2→1→4→13...，走到4的时候发现已经被标记，总步数是3+2=5，这是第一个碰到的公共节点，后面的公共节点总步数更大，所以返回4，和示例输出一致。

方法2：快慢指针+路径对齐（省空间） #

如果不想用额外空间存标记，可以利用环的特性：

1. 分别找出C1和C2路径的环入口（如果有环的话），以及各自路径的长度、环的长度。
2. 把两条路径对齐：让长路径的指针先往前走「两条路径长度差」的步数，然后两个指针一起走，第一个相遇的节点就是最近公共节点。
3. 如果其中一条路径走到死路还没相遇，就返回-1。

这个方法不用额外空间，但代码写起来稍微复杂一点，时间还是O(n)。

多次查询的优化 #

如果要处理很多组查询，可以提前预处理每个节点的路径信息：比如每个节点到环入口的距离、环里的节点列表等。这样每次查询的时间就能降到O(k)（k是两条路径里较短的那条的长度），最坏还是O(n)，但平均下来会快很多。

内容的提问来源于stack exchange，提问作者Cash flow