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 using Manhattan Distance, where distance(p1, p2) =
|p2.x - p1.x| + |p2.y - p1.y|
.
For example, given three people living at
(0,0)
, (0,4)
, and (2,2)
:1 - 0 - 0 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0
The point
(0,2)
is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.
Solution 1: best meeting point of one-dimension is at the middle point. for 2D is the same. find the mid-x and mid-y, it is the meeting place.
public class Solution {
public int minTotalDistance(int[][] grid) {
int m=grid.length;
if (m==0) return 0;
int n=grid[0].length;
int[] row=new int[n];
int[] col=new int[m];
for (int i=0;i<m;i++) {
for (int j=0; j<n;j++) {
if (grid[i][j]==1) {
col[i]++;
row[j]++;
}
}
}
int res=0;
int i=0, j=n-1;
while (i<j) {
int min=Math.min(row[i],row[j]);
res+=min*(j-i);
if ((row[i]-=min)==0) i++;
if ((row[j]-=min)==0) j--;
}
i=0; j=m-1;
while (i<j) {
int min=Math.min(col[i],col[j]);
res+=min*(j-i);
if ((col[i]-=min)==0) i++;
if ((col[j]-=min)==0) j--;
}
return res;
}
}
没有评论:
发表评论