求到一系列坐标距离和最小坐标的实现

[classicemi]

昨天睡前刷微博，看到有人发了这么一条：

面试题# 一个二维数组代表了城市中的坐标，给定N个人的坐标，求坐标使所有人走到这个坐标的距离的和最小，只可以横着或者竖着走，不可以斜着走。

为了简化这个模型，我们设定一个坐标原点为(0, 0)，每个人的坐标横纵坐标值都为非负整数，即坐标点都在坐标正半轴、原点或第一象限。

二维数组的限制条件全了，首先来实现一个生成二维数组的方法（限制坐标值都在100以内吧）：

function generator(length) {
    var result = [];
    for (var i = 0; i < length; i++) {
        result.push([Math.floor(Math.random() * 100), Math.floor(Math.random() * 100)]);
    }
    return result;
}

下面我们通过数学推导来获得距离和的表达式：
由于只能横着走或竖着走，那么距离和可以分解为横纵两个维度的和，先看水平方向的距离和：

distance_x = |x - x1| + |x - x2| + |x - x3| + ··· + |x - xn|

然后是垂直方向：

distance_y = |y - y1| + |y - y2| + |y - y3| + ··· + |y - yn|

同时由于两个维度互不干扰，因此可以分别求出最小值坐标后再合成一个点的坐标。又由于，横纵坐标距离和的表达式完全相同（只是变量名不同用以区分），那么两个维度上求最小值的方法也是一样的，分别求即可。这样我们就把问题简化到一个维度上了。

通过程序遍历的方式可以用傻瓜的方式计算距离之和，但是要使用遍历，就要给定遍历的起止条件，假设从 x1 到 xn 为单调递增，最小值为x1，最大值为xn。首先来证明所求坐标 x 的取值为 x1 <= x <= xn：

当 x = x1 时，由于 x1 是最小值：
    distance_x = |x1 - x1| + |x1 - x2| + |x1 - x3| + ··· + |x1 - xn|
                      = |x1 - x2| + |x1 - x3| + ··· + |x1 - xn|
                      = (x2 - x1) + (x3 - x1) + ··· + (xn - x1)
当 x = x1 -1 时：
    distance_x = |x1 - 1 - x1| + |x1 - 1 - x2| + |x1 - 1 - x3| + ··· + |x1 - 1 - xn|
                      = 1+ |x1 - 1 - x2| + |x1 - 1 - x3| + ··· + |x1 - 1 - xn|
                      = 1 + (x2 - x1 + 1) + (x3 - x1 + 1) + ··· + (xn - x1 + 1)
                      = (x2 - x1) + (x3 - x1) + ··· + (xn - x1) + 1 * (n - 1)
证得 x >= x1，同理可证 x <= xn，即 x1 <= x <= xn

这样，遍历的起止点分别 x1 和 xn，返回最小距离和的方法为：

function minDistanceCoordinate(coordinateArr) {
    var resolvedArray = resolveArray(coordinateArr),
        length = resolvedArray.length,
        xMin = Math.min.apply(this, resolvedArray[0]),
        xMax = Math.max.apply(this, resolvedArray[0]),
        yMin = Math.min.apply(this, resolvedArray[1]),
        yMax = Math.max.apply(this, resolvedArray[1]),
        result = [];

    result.push(singleDimensionDistance(xMin, xMax, resolvedArray[0]));
    result.push(singleDimensionDistance(yMin, yMax, resolvedArray[1]));

    return result;
}

其中用到了两个工具方法，分别是resolveArray和singleDimensionDistance。其中，resolveArray方法的作用是将每个点坐标值组成的二维数组解析成横坐标和纵坐标分别放在一个子数组里的二维数组，方法的实现如下：

function resolveArray(coordinateArr) {
    var result = [[], []];

    for (var i = 0, len = coordinateArr.length; i < len; i++) {
        result[0].push(coordinateArr[i][0]);
        result[1].push(coordinateArr[i][1]);
    }

    return result;
}

第二个singleDimensionDistance方法，它的作用是找出到一维数组中每个坐标值距离和最小的坐标值。实现如下：

function singleDimensionDistance(start, end, singleDimensionArray) {
    var result = 0,
        distance = end * singleDimensionArray.length,
        temp;

    for (var i = start; i <= end; i++) {
        temp = 0;
        for (var j = 0, len = singleDimensionArray.length; j < len; j++) {
            temp += Math.abs(i - singleDimensionArray[j]);
        }
        if (temp < distance) {
            distance = temp;
            result = i;
        }
    }

    return result;
}

我们来测试一下运算结果，执行如下代码：

var testArr = generator(10);
console.log(minDistanceCoordinate(testArr));

随机生成十个点坐标的二维数组：

[ [ 42, 14 ],
  [ 45, 62 ],
  [ 12, 47 ],
  [ 5, 99 ],
  [ 1, 10 ],
  [ 12, 45 ],
  [ 23, 40 ],
  [ 59, 85 ],
  [ 12, 66 ],
  [ 88, 72 ] ]

并进行计算，输出结果如下：

[ 12, 47 ]

多执行几次可以发现，求出的坐标点不一定是生成的十个点之一，但横纵坐标值都会和某个点的横纵坐标之一相同，继续观察可以发现，求出的横纵坐标值分别是所有横纵坐标的中位数。发现了这个规律之后再多想想，原来这是一道很简单的问题，你能用最简单的语言描述为什么吗？

[hlyzsm]

两点间线段最短嘛

[classicemi]

@hlyzsm 额，没太明白你的意思

[ldong]

可以想像成一個圓形, 然後這個 中位数 就相當是圓心, 半徑 r = sqrt(x^2 + y^2).

[classicemi]

@ldong 我大概明白你的意思，但是你的方式有没有什么严格证明的方法呢？