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)