今天刷力扣第376周赛，后三道题全是中位数贪心，之前从来没做过这种类型的题目，记录一下学习博客。
这里推荐灵神的视频讲解。
一个很经典的问题：
一个有序数组，寻找一个数字，使得所有数到达这个数的距离（数值差）最短。
举个极端的例子：
这个数字取数组的平均值:200，距离和是: 199 * 3 + (996 - 250) = 1343
这个数字取数组的中位数:1,距离和是：996 - 1
相较之下取中位数比平均数更短，但是为了严谨，还是简单证明一下：
1 3 5
如果取的数字在a0的左侧，那么如果这个数字加一依旧在a0的左侧，那么显而易见：总距离和会减少 n ；如果在an的右侧，也是同理。
如果取得数字在a0到a1之间如果该数字加一依旧在a0到a1之间，那么总距离就会减少 n - 1 - 1。如果是右侧(an-1 到 an之间)也是同理。
以此类推，到达中位数的时候就是最短距离。（平均数也可以用类似的方法推导）。简单证明。
难绷的是我想到了思路，但是代码一直写不出来，还是太菜了。最终代码还是抄的灵神代码（不得不说，写的比我那上不了台面的代码优雅的多）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| vector<int> palin;
auto init = [] {
for(int base = 1;base <= 10000;base*=10) {
for(int i = base;i < base * 10;i++) {
int num = i;
for(int m = i / 10;m;m /= 10) {
num = num * 10 + m % 10;
}
palin.push_back(num);
}
if(base <= 1000){
for(int i = base;i < base * 10;i++) {
int num = i;
for(int m = i;m;m /= 10) {
num = num * 10 + m % 10;
}
palin.push_back(num);
}
}
}
palin.push_back(1'000'000'001);
return 0;
}();
class Solution {
public:
long long minimumCost(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n = nums.size();
auto distance = [&](int i) -> long long {
long long sum = 0;
int target = palin[i];
for(auto& e : nums) {
sum += abs(e - target);
}
return sum;
};
int i = lower_bound(palin.begin(),palin.end(),nums[(n-1)/2]) - palin.begin();
if(palin[i] <= nums[n / 2]) return distance(i);
return min(distance(i),distance(i - 1));
}
};
|