LeetCode 296. 最佳的碰头地点（坐标独立+中位数的地方最近）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

有一队人（两人或以上）想要在一个地方碰面，他们希望能够最小化他们的总行走距离。

给你一个 2D 网格，其中各个格子内的值要么是 0，要么是 1。

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

示例： 输入: 1 - 0 - 0 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0输出: 6 解析: 给定的三个人分别住在(0,0)，(0,4) 和 (2,2):(0,2) 是一个最佳的碰面点，其总行走距离为 2 + 2 + 2 = 6，最小，因此返回 6。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/best-meeting-point
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

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

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;} };

8 ms 9.1 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 296. 最佳的碰头地点（坐标独立+中位数的地方最近）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。