296. Best Meeting Point - cocoder39/coco39_LC GitHub Wiki
notes 2023:
In case of 1d, the median minimizes the sum of absolute deviations. distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y| so the coordinate x and y are calculated independently. Thus we can use the medium of x and medium of y. For odd number of data points, the index of medium is len(rows) // 2. For even number of data points, the index of medium is either len(rows) // 2 or len(rows) // 2 -1. No matter which one we choose for even case, the final result is identical. (2 to 1, 2, 3, 4 vs 3 to 1, 2, 3, 4)
class Solution:
def minTotalDistance(self, grid: List[List[int]]) -> int:
rows, cols = [], []
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
rows.append(i)
cols.append(j)
rows.sort()
cols.sort()
res = 0
row, col = rows[len(rows)//2], cols[len(cols)//2]
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
res += abs(row-i) + abs(col-j)
return res
==============================================================================
Firstly think about solving this problem in 1-d. The median minimizes the sum of absolute deviations
T = O(m * n), S = O(m * n)
int minTotalDistance(vector<vector<int>>& grid) {
vector<int> x, y;
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j]) {
x.push_back(i);
y.push_back(j);
}
}
}
nth_element(x.begin(), x.begin() + x.size() / 2, x.end());
int median_x = x[x.size() / 2];
nth_element(y.begin(), y.begin() + y.size() / 2, y.end());
int median_y = y[y.size() / 2];
int res = 0;
for (int i = 0; i < x.size(); i++) {
res += abs(x[i] - median_x) + abs(y[i] - median_y);
}
return res;
}
std::nth_element (T = O(N)) is a partial sorting algorithm that rearranges elements in [first, last) such that:
- The element pointed at by nth is changed to whatever element would occur in that position if [first, last) was sorted.
- All of the elements before this new nth element are less than or equal to the elements after the new nth element.
a better solution with O(m * n) time and O(max(m, n)) memory. kinda bucket sort, x[i] is the number of people people live in row[i], y[j] is the number of people live in col[j]. Think in 1d first.
find out median is like finding out Center of gravity。
L R
position: 0 1 2 3 4 5 6 7
number: 2 3 4 5 3 5 1 4
we start from two ends, find right side is heavier, so left side should move one step towards right to get closer to center of gravity. thus the result increase by 2
L R
position: 0 1 2 3 4 5 6 7
number: 0 5 4 5 3 5 1 4
L R
position: 0 1 2 3 4 5 6 7
number: 0 5 4 5 3 5 5 0
L R
position: 0 1 2 3 4 5 6 7
number: 0 5 4 5 3 10 0 0
L R
position: 0 1 2 3 4 5 6 7
number: 0 0 9 5 3 10 0 0
L R
position: 0 1 2 3 4 5 6 7
number: 0 0 0 14 3 10 0 0
L R
position: 0 1 2 3 4 5 6 7
number: 0 0 0 14 13 0 0 0
C
position: 0 1 2 3 4 5 6 7
number: 0 0 0 27 0 0 0 0
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> x(m), y(n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
x[i] += grid[i][j]; //#people at position (i, ..)
y[j] += grid[i][j]; //#people at position (.., j)
}
}
return helper(x) + helper(y);
}
private:
int helper(vector<int>& nums) {
int res = 0;
int start = -1, end = nums.size();
int left_num = 0, right_num = 0;
while (start < end) {
if (left_num < right_num) {
res += left_num; //left_num people move one step towards right
left_num += nums[++start]; //now left_num people at position start
}
else {
res += right_num;
right_num += nums[--end];
}
}
return res;
}
};