https://leetcode-cn.com/problems/best-meeting-point/
/* 将问题分解成两个子问题,在一维上最近距离是所有点坐标的中位数,那么分别找到
x坐标的中位数和y坐标的中位数就是最佳碰头地点
*/
class Solution {
public int minTotalDistance(int[][] grid) {
List<Integer> rows = new ArrayList<>();
List<Integer> cols = new ArrayList<>();
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
if (grid[i][j] == 1) {
rows.add(i);
}
}
}
for (int i = 0; i < grid[0].length; ++i) {
for (int j = 0; j < grid.length; ++j) {
if (grid[j][i] == 1) {
cols.add(i);
}
}
}
int x = rows.get(rows.size() / 2);
int y = cols.get(cols.size() / 2);
int ans = 0;
for (int r : rows) {
ans += Math.abs(x - r);
}
for (int c : cols) {
ans += Math.abs(y - c);
}
return ans;
}
}