LeetCode刷题实战296：最佳的碰头地点 / 四六文摘

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最佳的碰头地点，我们先来看题面：

https://leetcode-cn.com/problems/best-meeting-point/

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated usingManhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

有一队人（两人或以上）想要在一个地方碰面，他们希望能够最小化他们的总行走距离。给你一个 2D 网格，其中各个格子内的值要么是 0，要么是 1。

1 表示某个人的家所处的位置。这里，我们将使用曼哈顿距离来计算，其中 distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|。

示例

解题

看的官方解答
两个方向的坐标是独立的，独立考虑
然后在中位数的点是总距离最近的
按序搜集横纵坐标，双指针，两端点相减的距离累加

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
      int m = grid.size(), n = grid[0].size(), i, j, dis = 0;
      vector<int> x, y;
      for(i = 0; i < m; ++i)
        for(j = 0; j < n; ++j)
          if(grid[i][j])
            x.push_back(i);
    for(j = 0; j < n; ++j)
      for( i = 0; i < m; ++i)
        if(grid[i][j])
          y.push_back(j);
    i = 0, j = x.size()-1;
    while(i < j)
      dis += x[j--]-x[i++];
    i = 0, j = y.size()-1;
    while(i < j)
      dis += y[j--]-y[i++];
    return dis;
    }
};