圆上点最小隔离点数求解：基于直径的高效算法技术问询

这是个经典的圆周点分布问题，我们可以把它转化为找能覆盖最多点的180度半圆，总点数减去这个最大值，就是单个半圆外最少被隔离的点数。这个思路能让我们用高效的算法处理大规模数据。

核心思路 #

单位圆上的直径对应一个180度的半圆区间。我们的目标是找到这样一个区间，让落在区间内的点尽可能多——反过来，区间外的点就最少。因为圆周是循环的，我们可以通过扩展数组的方式解决跨0度（或2π弧度）的边界问题。

高效算法步骤 #

1. 预处理角度 #

• 把所有点的角度统一转换到 [0, 360) 区间（如果用弧度就是 [0, 2π)），避免负数或超过360的情况。
• 对角度数组进行升序排序。
• 为了处理圆周的循环特性，把排序后的数组复制一份，每个元素加上360（或2π），得到一个长度为 2n 的扩展数组。比如原数组是 [30, 90, 270, 330]，扩展后就是 [30, 90, 270, 330, 390, 450, 630, 690]。

2. 滑动窗口找最大覆盖点数 #

用**双指针（快慢指针）**遍历扩展数组：

• 初始化左指针 i=0，右指针 j=0，最大覆盖数 max_count=0。
• 遍历每个左指针 i，移动右指针 j 直到 扩展数组[j] - 扩展数组[i] > 180（弧度则是 >π）停止。
• 此时窗口 [i, j-1] 内的点数就是 j - i，更新 max_count 为当前最大值。
• 左指针 i 右移一位，重复上述步骤直到遍历完原数组的所有元素（不用遍历扩展数组的后半部分，因为前n个已经覆盖了所有可能的起点）。

3. 计算最少隔离点数 #

最少被隔离的点数 = 总点数 n - max_count

复杂度分析 #

• 排序的时间复杂度是 O(n log n)，这是整个算法的瓶颈。
• 滑动窗口的遍历是 O(n)，因为每个元素最多被左、右指针各访问一次。
• 整体复杂度是 O(n log n)，完全适配大规模数据场景（比如n=1e5甚至1e6都能快速处理）。

关键注意事项 #

• 精度处理：如果角度是浮点数，判断差值是否≤180时要考虑精度误差，比如用 <= 180 + 1e-9（弧度则是 <= π + 1e-9），避免因浮点精度问题漏掉边界点。
• 重复角度：如果多个点角度完全相同，滑动窗口会自动包含所有重复点，不影响结果计算。
• 边界情况：
  • 所有点都在同一个半圆内：max_count = n，最少隔离点数为0。
  • 点均匀分布：比如4个点分别在0°、90°、180°、270°，此时最大覆盖数是3，最少隔离点数为1。

示例验证 #

比如给定角度数组 [30, 90, 270, 330]：

1. 排序后是 [30, 90, 270, 330]，扩展数组为 [30, 90, 270, 330, 390, 450, 630, 690]。
2. 滑动窗口遍历：
   • 当 i=3（对应角度330），j 可以移动到5（对应角度450=90+360），因为 450-330=120 ≤180，此时窗口内有3个点（330、30、90），max_count=3。
3. 最少隔离点数 = 4 - 3 = 1，符合预期（直径选在300°附近，270°被隔离，其余三个点在半圆内）。

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