给定坐标点集的最小成本曼哈顿距离求解优化方法咨询

问题回顾 #

给定坐标点列表x、y和对应的权重列表price，需要找到点(cx, cy)使得所有点到该点的加权曼哈顿总代价最小。总代价公式为：
总代价 = Σ(price[i] * (|x[i]-cx| + |y[i]-cy|))

核心优化思路 #

曼哈顿距离的总代价可以拆分为x轴方向代价和y轴方向代价的独立和：
总代价 = Σ(price[i] * |x[i]-cx|) + Σ(price[i] * |y[i]-cy|)
这意味着cx和cy的最优解可以分别计算，互不干扰——我们只需要分别找到x轴和y轴上的加权中位数即可。

加权中位数的定义 #

对于一维的加权距离问题Σ(w[i] * |a[i] - k|)，当k是加权中位数时，总距离最小。加权中位数的判定标准：将所有a[i]按从小到大排序后，累加权重，当累加和超过总权重的一半时，当前的a[i]就是加权中位数。

具体步骤 #

1. 计算总权重totalWeight = Σ(price[i])
2. 处理x轴方向：
   • 将x坐标与对应的price配对，按x值从小到大排序
   • 累加权重，找到第一个累加和≥totalWeight/2的x值，即为最优cx
3. 处理y轴方向：
   • 将y坐标与对应的price配对，按y值从小到大排序
   • 累加权重，找到第一个累加和≥totalWeight/2的y值，即为最优cy
4. 计算(cx, cy)对应的总代价并返回

时间复杂度分析 #

• 排序x和y坐标的时间：O(N log N)
• 寻找加权中位数和计算总代价的时间：O(N)
• 总时间复杂度：O(N log N)，相比暴力解法的O(10^8 * N)（约1e11次运算），效率提升几个数量级。

示例验证 #

输入：x = [1,3,2,4]，y = [1,2,3,4]，price=[1,3,2,4]

• 总权重：1+3+2+4=10，半值为5
• x轴排序后：(1,1), (2,2), (3,3), (4,4)，累加权重：1→3→6（≥5），故cx=3
• y轴排序后：(1,1), (2,3), (3,2), (4,4)，累加权重：1→4→6（≥5），故cy=3
• 总代价计算结果为17，与示例一致。

实现代码 #

import java.util.*;

public class OptimalPointFinder {
    public int solve(List<Integer> x, List<Integer> y, List<Integer> price) {
        int n = x.size();
        int totalWeight = price.stream().mapToInt(Integer::intValue).sum();
        
        // 找到x轴的加权中位数
        int cx = findWeightedMedian(x, price, totalWeight);
        // 找到y轴的加权中位数
        int cy = findWeightedMedian(y, price, totalWeight);
        
        // 计算总代价
        int totalCost = 0;
        for (int k = 0; k < n; k++) {
            int distance = Math.abs(x.get(k) - cx) + Math.abs(y.get(k) - cy);
            totalCost += price.get(k) * distance;
        }
        return totalCost;
    }
    
    private int findWeightedMedian(List<Integer> coords, List<Integer> weights, int totalWeight) {
        int n = coords.size();
        // 构建坐标与权重的配对列表
        List<Pair> pairs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            pairs.add(new Pair(coords.get(i), weights.get(i)));
        }
        // 按坐标从小到大排序
        pairs.sort(Comparator.comparingInt(p -> p.coord));
        
        int currentSum = 0;
        for (Pair pair : pairs) {
            currentSum += pair.weight;
            // 当累加和超过总权重的一半时，当前坐标即为加权中位数
            if (currentSum >= (totalWeight + 1) / 2) { // +1处理奇数权重的情况
                return pair.coord;
            }
        }
        // 理论上不会走到这里，因为总权重至少为1
        return pairs.get(0).coord;
    }
    
    // 辅助类存储坐标与权重
    private static class Pair {
        int coord;
        int weight;
        
        Pair(int coord, int weight) {
            this.coord = coord;
            this.weight = weight;
        }
    }
}

注意事项 #

• 当总权重为奇数时，取(totalWeight + 1)/2作为判定阈值，确保找到正确的中位数
• 若存在多个坐标满足累加和≥半值，任意选择其中一个即可，总代价相同

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