一维已排序带色点集的异色最近点对O(n)解法及分治方案咨询

问题回顾 #

给定已排序的一维整数点数组，每个点标记为红色或蓝色，需找出一对颜色不同的最近点对，要求时间复杂度为O(n)。

双指针解法（快速实现） #

因为数组已排序，任意非相邻点对的距离必然大于等于相邻点对的距离，因此只需遍历一次数组，检查每对相邻点：

• 初始化最小距离为无穷大，最优点对为空
• 从索引1开始遍历数组，比较当前点与前一个点的颜色：
  • 若颜色不同，计算两点间的距离
  • 若该距离小于当前最小距离，更新最小距离与最优点对
• 遍历结束后返回最优结果
  该解法时间复杂度O(n)，空间复杂度O(1)，实现简单直观。

分治解法（满足O(n)时间要求） #

分治思路的核心是将数组递归划分为左右子数组，分别求解子问题的最优解，再处理跨左右子数组的潜在最优解，最终合并结果。

步骤详解 #

1. 基线情况

   • 若数组长度为1：无有效点对，返回无穷大距离与空点对
   • 若数组长度为2：检查两点颜色是否不同，不同则返回两点距离与该点对；否则返回无穷大距离与空点对

2. 递归划分

   • 取数组中点mid = n // 2，将数组划分为左子数组arr[0..mid-1]和右子数组arr[mid..n-1]
   • 递归求解左子数组的最优距离d1与点对p1，右子数组的最优距离d2与点对p2
   • 初始化当前最优距离d = min(d1, d2)，最优点对p为对应p1或p2

3. 跨区域检查
   由于数组已排序，左子数组的所有点值均≤右子数组的点值，跨区域的潜在最优点对只能是左子数组的最后一个点arr[mid-1]与右子数组的第一个点arr[mid]：

   • 若两点颜色不同，计算距离dist = arr[mid].val - arr[mid-1].val
   • 若dist < d，则更新d为dist，p为该点对
   • 无需检查其他跨区域点对：因为左右子数组内部的最小距离均≥d，其他跨区域点对的距离必然≥d（例如arr[mid-2]与arr[mid]的距离 = (arr[mid-1]-arr[mid-2]) + (arr[mid]-arr[mid-1]) ≥ d + dist > d）

4. 返回结果
   返回最终的最小距离d与对应的点对p

时间复杂度分析 #

递归式为T(n) = 2*T(n/2) + O(1)，根据主定理，该递归式的时间复杂度为O(n)，符合题目要求。

内容的提问来源于stack exchange，提问作者Chris c