https://leetcode.com/problems/best-meeting-point/description/
这道题首先暴力解,就是针对每个空地,做一个BFS,看分别每个1的距离和加起来。这样算出每个空点后的距离,再所有空地里取个最小值。时间复杂度(m2*n2)
如果K(代表1)比较少的话,我们先存下K的坐标。然后让每一个空地的坐标,依次和K的坐标,去算曼哈顿距离,这是O1的。所以可以优化到O(MNK)
当然如果K是(m*n/2) 那么时间复杂度还是一样。
随后我们想如果考虑一维坐标。什么情况下那个点到所有点的距离最小。
必然是这个点分割后,左右2边的点数目一致,或最接近一致。为什么。因为如果不一致,你往点多的那个方向移。那距离和的变化,就是所有少的那一边的点,距离都要+1,假设少的点的个数是K,多的是J。多的那一边的点距离都要-1.
那么总距离的变化就是SUM+k-j,j>k 所以可以使得SUM更小。
有了这个思路,我们就可以分别求一次水平的,再求一次竖直的应该选的坐标。
这2个坐标就能点出来。2个距离和加起来就是解。
时间复杂度(M*N+M+N)
public int minTotalDistance(int[][] ctxs) {
int h = ctxs.length;
int l = ctxs[0].length;
int[] hor = new int[l];
int[] ver = new int[h];
int cntHor = 0;
int cntVer = 0;
int cnt = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < l; j++){
if(ctxs[i][j] == 1){
cntHor += j;
cntVer += i;
cnt++;
hor[j]++;
ver[i]++;
}
}
}
int minHor = cntHor;
int minVer = cntVer;
int sum = 0;
for(int i = 1; i < l; i++){
sum += hor[i-1];
cntHor+=sum-(cnt-sum);
minHor = Math.min(minHor,cntHor);
}
sum = 0;
for(int i = 1; i < h; i++){
sum += ver[i-1];
cntVer+=sum-(cnt-sum);
minVer = Math.min(minVer,cntVer);
}
return minHor+minVer;
}