题解一: 数学方法
题解思路: 首先,给出结论给定N个点(x1,x2...xn),要找到使得 :
图片说明
最小得x; 此点比然是其中位数。
证明:首先对N个点排序.假设该点在N个点中xi:
图片说明
如果这个点往右移xi+1
图片说明
两者相减,可得向右移距离变化:
图片说明
xi+1-x1始终大于零,所以当i<=n/2时,(2i - n)小于等于0 上式大于等于0; 当i>=n/2时,(2i-n)大于等于0 上式小于等于0; 随着i逐渐增大,距离先小后大。所以在i = n/2取得最小值。
假设该点不在这N个点中: xi<t1<t2<xi+1,得
图片说明
当i<= n/2 , 上式大于等于0,当i>=n/2, 上式小于等于0; 距离先小后大,所以在i = n/2取得最小值。
复杂度分析:
时间复杂度: ,排序时间
空间复杂度: ,需要申请辅助数组,来保存x,y的值,来进行排序
实现如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param n int整型 n
     * @param x int整型vector x
     * @param y int整型vector y
     * @param w int整型vector w
     * @return long长整型
     */
    long long MinimumDistance(int n, vector<int>& x, vector<int>& y, vector<int>& w) {
        // write code here
        vector<int> xt; 
        vector<int> yt;
        for(auto it :x) xt.push_back(it); 
        for(auto it :y) yt.push_back(it);
        sort(xt.begin(),xt.end());  //对x排序
        sort(yt.begin(),yt.end());   //对y排序
        int xlen = x.size(),ylen = y.size();
        double x1 = 0,y1=0;
        int mid1 = xlen/2;
        if(xlen%2==0){
            x1 = xt[mid1]+xt[mid1-1];  //如果长度为偶数,求x中位数
            y1 = yt[mid1]+yt[mid1-1];  
            x1 /= 2;
            y1 /= 2;
        }else {x1 = xt[mid1];y1 = yt[mid1];} 
        double ans = 0;
        for(int i = 0;i<xlen;++i){
           double dis = abs(x1-x[i])+abs(y1-y[i]);  //求距离
           ans += dis*w[i];  //乘上权重
        }
        return (long long)ans;
    }
};

题解二:二分
题解思路 : x,y都可以看出单独计算曼哈顿距离。假设有N个数,并且当前位置为mid,mid左边有x,那么右边有n-x. 假设当前带权曼哈顿距离为dis,如果该点向右移动,新曼哈顿距离为res+z(2x-n);
*
复杂度:**
时间复杂度: : x和y都是单层遍历
空间复杂度: :需要申请辅助数组nums_weight的大小
实现如下:

class Solution {
public:
    long long Manhattandistance(int n, vector<int>& m, vector<int>& w, int max_value){
        long long sum = 0, temp = 0, distance = 0;
        int median;
        vector<long long> nums_weight(max_value + 1, 0);
        for(int i = 0; i < n; i++){
            nums_weight[m[i]] += w[i]; 
            sum += w[i];
        }
        for(int i = 0; i <= max_value; i++){ //找权值中点
            temp += nums_weight[i];
            if(temp >=  sum / 2){
                median = i;
                break;
            }
        }
        for(int i = 0; i < n; i++)
            distance += abs(m[i] - median) * w[i];  //计算带权曼哈顿距离
        return distance;
    }
    long long MinimumDistance(int n, vector<int>& x, vector<int>& y, vector<int>& w) {
        int max_x = 0, max_y = 0;
        for(int i = 0; i < n; i++){ //分别找到 x y 最大值
            max_x = max(max_x, x[i]);
            max_y = max(max_y, y[i]);
        }
        //x维加上y维带权曼哈顿距离
        return Manhattandistance(n, x, w, max_x) + Manhattandistance(n, y, w, max_y);
    }
};