oavoservice 原創復盤：重點在「如何把候選縮到常數個」，以及 tie-break 的實作細節。
題目（改寫版）
給定 n 個城市座標：(x[i], y[i])，以及 q 個查詢城市名。
對每個查詢城市 c：
- 在所有 x 相同 或 y 相同 的城市裡，找到與
c的曼哈頓距離最小的那個。 - 若距離相同，返回名字字典序更小的。
- 若不存在同軸城市，返回
"NONE"。
思路核心
如果每次查詢都掃一遍 n，會變成 O(nq)。
優化：
- 把同一條豎線（相同 x）上的城市按 y 排序
- 把同一條橫線（相同 y）上的城市按 x 排序
對查詢城市，只需要在兩條有序列表裡找它的相鄰前驅/後繼，最多比較 4 個候選。
資料結構
name -> (x, y)x_map[x] = [(y, name), ...]（按 y, 再按 name 排序）y_map[y] = [(x, name), ...]（按 x, 再按 name 排序）
複雜度
- 預處理：
O(n log n) - 單次查詢：
O(log n)
Python 參考實作
from bisect import bisect_left
from collections import defaultdict
def closest_straight_city(names, xs, ys, queries):
pos = {}
x_map = defaultdict(list)
y_map = defaultdict(list)
for name, x, y in zip(names, xs, ys):
pos[name] = (x, y)
x_map[x].append((y, name))
y_map[y].append((x, name))
for x in x_map:
x_map[x].sort() # (y, name)
for y in y_map:
y_map[y].sort() # (x, name)
def pick_best(candidates, x0, y0):
best = None
best_dist = None
for name, x, y in candidates:
dist = abs(x - x0) + abs(y - y0)
if best is None or dist < best_dist or (dist == best_dist and name < best):
best = name
best_dist = dist
return best
ans = []
for q in queries:
if q not in pos:
ans.append("NONE")
continue
x0, y0 = pos[q]
candidates = []
# 同 x：在按 y 排序列表裡找鄰居
lst = x_map.get(x0, [])
i = bisect_left(lst, (y0, q))
for j in (i - 1, i + 1):
if 0 <= j < len(lst):
y, name = lst[j]
if name != q:
candidates.append((name, x0, y))
# 同 y：在按 x 排序列表裡找鄰居
lst = y_map.get(y0, [])
i = bisect_left(lst, (x0, q))
for j in (i - 1, i + 1):
if 0 <= j < len(lst):
x, name = lst[j]
if name != q:
candidates.append((name, x, y0))
best = pick_best(candidates, x0, y0)
ans.append(best if best is not None else "NONE")
return ans
常見坑
bisect_left的 key 需要包含 name，避免同座標時定位不穩定。- 候選只需鄰居（前驅/後繼），不要掃整條線。
- tie-break：距離相同選字典序更小。
如果你在準備 DoorDash VO，這題在面試裡常被用來考你是否能把「全域掃描」改造成「索引 + 鄰居候選」。oavoservice 會重點訓練這種「把候選縮到常數個」的套路。
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。