2024-07-03
1509. Minimum Difference Between Largest and Smallest Value in Three Moves
You are given an integer array nums.
In one move, you can choose one element of nums and change it to any value.
Return the minimum difference between the largest and smallest value of nums
after performing at most three moves.
题目要求减少最大跟最小的差距
所以要嘛把最大砍掉 要嘛把最小砍掉
可以砍3次
大大大 -> nums[0] 跟 nums[(n-1)-3] 的差距
大大小 -> nums[1] nums[(n-1)-2]
大小小
小小小
4种组合
sorting 以后暴力算出来
int minDifference(vector<int>& nums) {
if (nums.size() <= 4) {
return 0;
}
sort(nums.begin(), nums.end());
int v1 = nums[nums.size() - 4] - nums[0];
int v2 = nums[nums.size() - 3] - nums[1];
int v3 = nums[nums.size() - 2] - nums[2];
int v4 = nums[nums.size() - 1] - nums[3];
return min(min(v1, v2), min(v3, v4));
}
如果是浮动k的话
可能会是用loop跑num[r-i]-num[i], i=0...k
另外看速度100%的发现其实中间根本不重要
只要看最大最小各k个
所以他先挑了最大k个跟最小k个
只要排2k个不用全排
从O(nlogn)变成O(nk+klogk)=O(n) (k<<n)