public class Solution {
public int minTotalDistance(int[][] grid) {
if(grid == null || grid.length == 0) return 0;
List<Integer> listX = new ArrayList<>();
List<Integer> listY = new ArrayList<>();
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == 1){
listX.add(i);
listY.add(j);
}
}
}
int medianX = findMedian(listX, 0, listX.size() - 1);
int medianY = findMedian(listY, 0, listY.size() - 1);
int minDis = 0;
for(int x : listX){
minDis += Math.abs(medianX - x);
}
for(int y : listY){
minDis += Math.abs(medianY - y);
}
return minDis;
}
private int findMedian(List<Integer> list, int start, int end){
int pivot = list.get(start);
int left = start;
int right = end;
while(left <= right){
while(left <= right && list.get(left) <= pivot) left++;
while(left <= right && list.get(right) >= pivot) right--;
if(left < right) swap(list, left, right);
}
swap(list, start, right);
int medianIndex = list.size() / 2;
if(right == medianIndex){
return list.get(right);
} else if(right < medianIndex){
return findMedian(list, right + 1, end);
} else {
return findMedian(list, start, right - 1);
}
}
private void swap(List<Integer> list, int a, int b){
int temp = list.get(a);
list.set(a, list.get(b));
list.set(b, temp);
}
}
论坛上还有一个很有趣的解法，虽然时间复杂度不好看，但是思路巧妙，简洁易懂。
核心思想在于，最优 meeting point 一定是在所有点的中间，而对于每个 pair ，他们到 best meeting point 的距离和就是 pair 两点的区间长度，所以假设以 0 为远点，用双指针检查每一对就可以了。
public int minTotalDistance(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
List<Integer> I = new ArrayList<>(m);
List<Integer> J = new ArrayList<>(n);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 1){
I.add(i);
J.add(j);
}
}
}
return getMin(I) + getMin(J);
}
private int getMin(List<Integer> list){
int ret = 0;
Collections.sort(list);
int i = 0;
int j = list.size() - 1;
while(i < j){
ret += list.get(j--) - list.get(i++);
}
return ret;
}
public class Solution {
public int minTotalDistance(int[][] grid) {
int m = grid.length, n = grid[0].length;
List<Integer> I = new ArrayList<Integer>();
List<Integer> J = new ArrayList<Integer>();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1) {
I.add(i);
}
}
}
for(int j = 0; j < n; j++) {
for(int i = 0; i < m; i ++) {
if(grid[i][j] == 1) {
J.add(j);
}
}
}
return minTotalDistance(I) + minTotalDistance(J);
}
public int minTotalDistance(List<Integer> grid) {
int i = 0, j = grid.size() - 1, sum = 0;
while(i < j) {
sum += grid.get(j--) - grid.get(i++);
}
return sum;
}
}
一个非常土的办法是，先扫一遍矩阵，找到 k 个起始点；对于每一个起始点开始做 BFS，记录到每一个其他格子的距离，每次扫完了要存这个位置到起点的距离，并且每次扫完一个点要恢复矩阵的访问状态，免得下一次扫描出错，扫到第 k 个起点的时候，把每个 cell 里面的相对于其他店的距离加起来，保持一个 min 就可以了。
时间复杂度： 2k * O(mn) ，考虑到 k 可能等于整个矩阵，其实是 O(m^2 * n^2)
空间复杂度： k * O(mn)，考虑到 k 可能等于整个矩阵，其实时 O(m^2 * n^2)
我觉得这个思路可以不用写代码了，肯定要超时的。。
这个时间复杂度和暴力解 Walls and Gates 一样，不难想到，可以试着从每个 "1" 出发，去反过来探索矩阵。 假如我们记录了这 k 个起始点，我们可以依次 bfs 每一个起始点 / 该起始点的范围，一次一个点，一次扩张一轮，当 k 个点的 “势力范围” 第一次相交的时候，就是我们要找的最优起点。有了最优起点，O(mn) 的时间显然就可以算出最短距离。