如何修改迭代选取最远节点算法解决重复选点问题

你的代码出现重复选点、结果错误，由4个核心bug导致：

• 初始放入pickedNodes的2个启动节点没有从候选集allNodes中移除，遍历候选节点时会把已选节点重新纳入计算，直接导致重复选取
• 距离计算方法存在低级笔误：Math.hypot(a.x - b.x, a.x - b.x)第二个参数错误传入x轴差值，完全没有计算y轴差距，节点数量增多、x坐标分布密集时距离结果完全失真
• 查找最远节点的时机错误：你把Collections.max查找逻辑写在了遍历已选节点的循环内部，每遍历一个已选节点就重新查一次最大值，此时还没算完所有候选节点到全部已选节点的距离，拿到的根本不是全局最远点
• 类型不匹配导致计算异常：你用Integer类型存距离，但Math.hypot返回值是double，不仅会丢失小数精度，距离值超过整数范围时还会出现溢出反转，进一步打乱距离排序。

这个选点逻辑是经典的最远点采样，不需要每次迭代都遍历所有历史已选节点做重复计算，按照以下逻辑修改即可：

• 正式迭代前先把初始已选节点从候选集移除，避免重复选择
• 修正距离计算的笔误，把Node类的distance属性类型统一改为double，避免精度和溢出问题
• 初始化阶段先计算所有候选节点到初始两个已选节点的距离，这里默认存每个候选节点到最近已选节点的距离（这是最远点采样的标准实现，选点覆盖性最好；如果你要存到任意已选节点的最大距离，只需要把比较符号反转即可）
• 每轮迭代先找当前距离值最大的候选节点，加入已选集合后从候选集移除
• 后续迭代不需要重新遍历所有已选节点，只用新加入的节点更新剩余候选节点的距离值即可，能把时间复杂度从O(k²n)降到O(kn)

// 第一步：把初始已选节点从候选池移除，从根源避免重复选点
allNodes.removeAll(pickedNodes);
// 初始化所有候选节点的距离为最大值，用于计算到最近已选节点的距离
for (Node node : allNodes) {
    node.distance = Double.MAX_VALUE;
}

// 基于初始两个已选节点，计算所有候选节点的初始最近距离
for (Node picked : pickedNodes) {
    for (Node candidate : allNodes) {
        double currentDist = distanceBetween(candidate, picked);
        if (currentDist < candidate.distance) {
            candidate.distance = currentDist;
        }
    }
}

int needPick = k - pickedNodes.size();
while (needPick > 0 && !allNodes.isEmpty()) {
    // 所有候选节点距离更新完成后，再查找全局最远节点
    Node farthestNode = Collections.max(allNodes, Comparator.comparingDouble(n -> n.distance));

    // 标记节点状态，更新已选集合和候选集合
    farthestNode.setPicked(true);
    pickedNodes.add(farthestNode);
    allNodes.remove(farthestNode);
    needPick--;

    if (needPick == 0) break;

    // 仅用新加入的节点更新剩余候选的距离，不需要重复遍历历史已选节点
    for (Node candidate : allNodes) {
        double newDist = distanceBetween(candidate, farthestNode);
        if (newDist < candidate.distance) {
            candidate.distance = newDist;
        }
    }
}

// 修正后的欧氏距离计算方法，注意y轴差值的计算
private double distanceBetween(Node a, Node b) {
    return Math.hypot(a.x - b.x, a.y - b.y);
}

• 如果你需要的逻辑确实是“选择到任意一个已选节点距离最大的点”，只需要做两处调整：初始化时把节点distance设为Double.MIN_VALUE，距离更新时把判断条件的<改为>即可，其余流程不变
• 如果节点总量很大，建议把allNodes换成HashSet存储，减少remove操作的时间开销，注意给Node类重写equals和hashCode方法即可。

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