296. Best Meeting Point

问题来自 296. Best Meeting Point

---

这道题是“二维邮局问题”。对于这道题我需要申明一点：meeting point可以是grid[i][j]值为1的地方，意思是这个人就在自己家和其他所有人见面。

我们先从简单的问题分析。假设在一维的数轴上有n个人(p[0]表示x值最小的那个人，p[1]次小，…..，即认为我们已经按照x值排好序了)，选一个meeting point使得total distance（所有人到这个meeting point的距离和）最小。继续简化：

1. 如果n等于1：那么这个人自己家就是meeting point, 即p[0]
2. 如果n等于2：那么p[0]到p[1]的线段上任何一点都可以是meeting point。可以证明以线段内任一点为meeting point得到的shortest total distance和取线段端点为meeting point得到的值是相等的，因此我们选p[0]
3. 如果n等于3：那么meeting point是p[1]
4. 如果n等于4：那么meeting point可以是p[1]也可以是p[2]
5. 如果n等于5：那么meeting point是p[2]
6. 如果n等于6：那么meeting point可以是p[2]也可以是p[3]
7. ………..

可以看出，meeting point就是index为中点的那个人的家里（注意，是x值排序后，序号的中点，不是(p[n-1]-p[0])/2).

接着再来看看我们这个“二维邮局”问题：其实很容易，我们只要选一个点，这个点的x值满足上面描述的，这个点的y值同样描述上面描述的。所以做法很简单，构造x数组和y数组，分别sort in ascending order。选中mid点即可，然后求距离即可。x的选取不会和y的选取冲突。

---

class Solution {
public:
    int minTotalDistance(vector<vector<int> >& grid) {
        int row = grid.size();
        if(row == 0) return 0;
        int col = grid[0].size();
        if(col == 0) return 0;
        
        vector<int> x;
        vector<int> y;
        for(int r = 0; r < row; ++r)
            for(int c = 0; c < col; ++c)
                if(grid[r][c] == 1)
                {
                    x.push_back(r);
                    y.push_back(c);
                }
        
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        
        int total = 0;
        int size = x.size();
        int mid = size/2;
        for(int i = 0; i < size; ++i)
        {
            if(i <= mid)
                total += x[mid]-x[i]+y[mid]-y[i];
            else
                total += x[i]-x[mid]+y[i]-y[mid];
        }
        
        return total;
    }
};

当然上面最后求距离的时候我们也可以这么写：

class Solution {
public:
    int minTotalDistance(vector<vector<int> >& grid) {
        int row = grid.size();
        if(row == 0) return 0;
        int col = grid[0].size();
        if(col == 0) return 0;
        
        vector<int> x, y;
        for(int r = 0; r < row; ++r)
            for(int c = 0; c < col; ++c)
                if(grid[r][c] == 1)
                {
                    x.push_back(r);
                    y.push_back(c);
                }
        
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        int low = 0, high = x.size()-1, result = 0;
        while(low < high)
        {
            result += x[high]-x[low] + y[high]-y[low];
            ++low;
            --high;
        }
        
        return result;
    }
};

Java:

public class Solution {
    public int minTotalDistance(int[][] grid) {
        int row = grid.length;
        if(row == 0) return 0;
        int col = grid[0].length;
        if(col == 0) return 0;
        
        List<Integer> x = new ArrayList<Integer>();
        List<Integer> y = new ArrayList<Integer>();
        for(int r = 0; r < row; ++r)
            for(int c = 0; c < col; ++c)
                if(grid[r][c] == 1)
                {
                    x.add(r);
                    y.add(c);
                }
                
        Collections.sort(x);
        Collections.sort(y);
                
        int size = x.size();
        int mid = size/2;
        int total = 0;
        
        for(int i = 0; i < size; ++i)
            if(i <= mid)
                total += x.get(mid)-x.get(i)+y.get(mid)-y.get(i);
            else
                total += x.get(i)-x.get(mid)+y.get(i)-y.get(mid);
                
        return total;
    }
}