题解 | #航海#

题解一： 数学方法
题解思路： 首先，给出结论给定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);
    }
};