这题的关键在于二维矩阵的一维化。
我们可以把row 和col decouple
然后分别解决row的问题和col的问题
对row的问题， 我们其实是求的它的中位数
1、中位数的性质
给定一个数列，中位数有这样的性质 ：所有数与中位数的绝对差之和最小
这个可以用 quickSelect来做，但完全没有必要。
我们不知道的话就扫一遍array求最小值就知道了，复杂度是O(N)的 。
一遍过bug free
class Solution {
public int minTotalDistance(int[][] grid) {
int N = grid.length, M = grid[0].length;
int[] col1d = new int[M];
int[] row1d = new int[N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < M; c++) {
col1d[c] += grid[r][c];
row1d[r] += grid[r][c];
}
}
return minDistance(col1d) + minDistance(row1d);
}
private int minDistance(int[] array) {
int N = array.length;
int cand = 0;
int sum = 0;
for (int i = 0; i < array.length; i++) {
cand += i * array[i];
sum += array[i];
}
int best = cand;
int traversedSum = array[0];
for (int i = 1; i < array.length; i++) {
cand += traversedSum;
cand -= (sum - traversedSum);
best = Math.min(best, cand);
traversedSum += array[i];
}
return best;
}
}
