难度: Hard
Submission
运行时间: 146 ms
内存: 36.7 MB
class Solution:
def beautifulPair(self, nums1: List[int], nums2: List[int]) -> List[int]:
def dist(x1: int, y1: int, x2: int, y2: int) -> int:
return abs(x1 - x2) + abs(y1 - y2)
def dfs(l: int, r: int):
if l >= r:
return inf, -1, -1
m = (l + r) >> 1
x = points[m][0]
d1, pi1, pj1 = dfs(l, m)
d2, pi2, pj2 = dfs(m + 1, r)
if d1 > d2 or (d1 == d2 and (pi1 > pi2 or (pi1 == pi2 and pj1 > pj2))):
d1, pi1, pj1 = d2, pi2, pj2
t = [p for p in points[l : r + 1] if abs(p[0] - x) <= d1]
t.sort(key=lambda x: x[1])
for i in range(len(t)):
for j in range(i + 1, len(t)):
if t[j][1] - t[i][1] > d1:
break
pi, pj = sorted([t[i][2], t[j][2]])
d = dist(t[i][0], t[i][1], t[j][0], t[j][1])
if d < d1 or (d == d1 and (pi < pi1 or (pi == pi1 and pj < pj1))):
d1, pi1, pj1 = d, pi, pj
return d1, pi1, pj1
pl = defaultdict(list)
for i, (x, y) in enumerate(zip(nums1, nums2)):
pl[(x, y)].append(i)
points = []
for i, (x, y) in enumerate(zip(nums1, nums2)):
if len(pl[(x, y)]) > 1:
return [i, pl[(x, y)][1]]
points.append((x, y, i))
points.sort()
_, pi, pj = dfs(0, len(points) - 1)
return [pi, pj]
Explain
该题解使用分治法和归并排序的思想来解决问题。首先将所有点按照 x 坐标排序，然后递归地将点集划分为左右两个子集，分别求解子问题。在合并时，对于横跨左右子集的点对，可以通过维护一个纵坐标有序的点集，在一定范围内枚举所有可能的点对，更新全局最优解。最后返回距离最小的一对点的下标。
时间复杂度: O(nlog^2n)
空间复杂度: O(nlogn)
class Solution:
def beautifulPair(self, nums1: List[int], nums2: List[int]) -> List[int]:
def dist(x1: int, y1: int, x2: int, y2: int) -> int:
# 计算曼哈顿距离
return abs(x1 - x2) + abs(y1 - y2)
def dfs(l: int, r: int):
if l >= r:
return inf, -1, -1
m = (l + r) >> 1
x = points[m][0]
# 递归求解左右子问题
d1, pi1, pj1 = dfs(l, m)
d2, pi2, pj2 = dfs(m + 1, r)
# 合并子问题的解
if d1 > d2 or (d1 == d2 and (pi1 > pi2 or (pi1 == pi2 and pj1 > pj2))):
d1, pi1, pj1 = d2, pi2, pj2
# 获取横跨左右子集的点
t = [p for p in points[l : r + 1] if abs(p[0] - x) <= d1]
t.sort(key=lambda x: x[1])
# 枚举横跨左右子集的点对，更新最优解
for i in range(len(t)):
for j in range(i + 1, len(t)):
if t[j][1] - t[i][1] > d1:
break
pi, pj = sorted([t[i][2], t[j][2]])
d = dist(t[i][0], t[i][1], t[j][0], t[j][1])
if d < d1 or (d == d1 and (pi < pi1 or (pi == pi1 and pj < pj1))):
d1, pi1, pj1 = d, pi, pj
return d1, pi1, pj1
pl = defaultdict(list)
for i, (x, y) in enumerate(zip(nums1, nums2)):
pl[(x, y)].append(i)
points = []
for i, (x, y) in enumerate(zip(nums1, nums2)):
if len(pl[(x, y)]) > 1:
return [i, pl[(x, y)][1]]
points.append((x, y, i))
points.sort()
_, pi, pj = dfs(0, len(points) - 1)
return [pi, pj]
Explore
在分治法中，选择以x坐标来排序并划分点集是为了简化问题的复杂性并高效地处理距离计算。这种方法基于最近点对问题的典型解法，其中按照x坐标排序可以帮助我们在递归分治过程中容易地将点集划分为相对独立的左右两部分。这样做的好处是在合并步骤中，可以有效地限制需要考虑的点对的数量，因为横跨左右子集的点对的潜在最小距离将受到左右子集内部点对距离的影响。如果我们选择排序和分割的其他属性，比如y坐标，虽然理论上可行，但在处理跨越分界线的点对时可能需要考虑更多的点，这增加了问题的复杂度。
在递归处理过程中，当点集只剩下一个点时，显然无法形成点对，因此返回的距离是无穷大（inf），以及无效的点对下标（-1, -1）。这种返回值在上层递归中用于判断和处理。当这样的返回值被合并到上层递归中时，任何有效的点对（即距离不是无穷大的点对）都将比这个返回值更优，因此这个返回值不会影响到最终的最小距离的计算。上层递归会忽略这个无效的点对，只考虑有效的点对进行距离比较和最小值更新。
在处理横跨左右子集的点对时，限制纵坐标的差值不超过已知的最小距离d1是基于距离的上界考虑。这种方法基于一个观察：如果两点的纵坐标之差大于d1，则无论它们的横坐标如何，它们之间的曼哈顿距离必然大于d1。因此，这种情况下，这对点不可能成为新的最近点对。虽然这种方法在理论上可能看起来有风险，但由于曼哈顿距离的定义（两点间距离等于它们在每个坐标维度上差的绝对值之和），这种策略实际上是安全的，并不会漏掉任何可能的最近点对。