[Leetcode] 296. Best Meeting Point

 

这一题我们先需要把它简化成一维来看。如果给你一列x坐标，那么找一个点，这列x坐标距离这个点的总和是最近的。那么这个点在哪呢，答案是他们的中位点，也就是譬如你有n个点，那么它就在前面n / 2个点和后面n / 2个点中间的任意一个位置。或者如果n是奇数的话，那就是最中间的那个点（非距离上的，是从左到右的顺序上的中间点）。假设这个点为i，那么这个距离总和就是点i - 1和点i + 1的距离加上点i - 2 和点i + 2的距离加上点.....最后加上点1和点n的距离。

这一题，其实就是这么一个原理的延申。简单来说就是把每个点分拆成x坐标和y坐标上的一维点集合，然后分别进行上面的处理。你可以理解为，所有点，先都走到一个同一条x轴（或y轴），然后再走到一个点上。所以其实就是做一个x轴的一维计算再做一个y轴的一维计算就好了。

    public int minTotalDistance(int[][] grid) {
        ArrayList<Integer> xCords = new ArrayList<>();
        ArrayList<Integer> yCords = new ArrayList<>();
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    xCords.add(i);
                    yCords.add(j);
                }
            }
        }
        
        return this._calculateDist(xCords) + this._calculateDist(yCords);
    }
    
    private int _calculateDist(ArrayList<Integer> cords) {
        Collections.sort(cords);
        int head = 0, tail = cords.size() - 1;
        int result = 0;
        while (head < tail) {
            result += cords.get(tail) - cords.get(head);
            tail--;
            head++;
        }
        
        return result;
    }