​LeetCode刷题实战296：最佳的碰头地点

今天和大家聊的问题叫做 最佳的碰头地点，我们先来看题面：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;
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。