https://leetcode.com/problems/minimum-operations-to-make-a-uni-value-grid/
考察一个数学知识,如何找到距离所有点之和距离最近的点
use std::collections::HashMap;
use std::cmp;
impl Solution {
pub fn min_operations(grid: Vec<Vec<i32>>, x: i32) -> i32 {
let mut arr: Vec<i32> = grid.iter().flatten().cloned().collect();
arr.sort();
let mid = arr[(arr.len() - 1) / 2];
let mut res = 0;
for &y in arr.iter() {
if y == mid {
continue;
}
let diff = (y - mid).abs();
if diff % x != 0 {
return -1;
}
res += diff / x;
}
res
}
}
https://asvrada.github.io/blog/median-shortest-distance-sum/
记住结论,一维空间,距离所有点最近的点,就是最中间那个点
其实就是让两边一样多,最中间的两个之间的数(含)都可以,这样移动到这个点的代价最小
另外,Rust刷题比较难受,效率也比较着迷,试着熟悉上手吧,不能被Python惯坏了。