?LeetCode刷題實(shí)戰(zhàn)296：最佳的碰頭地點(diǎn)
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|.
示例
解題
看的官方解答
兩個(gè)方向的坐標(biāo)是獨(dú)立的，獨(dú)立考慮
然后在中位數(shù)的點(diǎn)是總距離最近的
按序搜集橫縱坐標(biāo)，雙指針，兩端點(diǎn)相減的距離累加
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;
}
};