1509. Minimum Difference Between Largest and Smallest Value in Three Moves
有一个array nums
在一个move中，可以选择nums中的一个元素将他改成任意数值
最多可以做三次move
请问做完move后nums中最大和最小元素的差值
思路:
先将nums排序
然后3次move会有4种可能
(1)改最大的三个元素
(2)改最大的两个元素和最小的一个元素
(3)改最大的一个元素和最小的两个元素
(4)改最小的三个元素
最后求出这4种可能中最大值和最小值的差值
其中最小的就是解答
C Code :
#define Min(x,y)(x<y?x:y)
void quick(int* nums, int numsSize){
if(numsSize<=1){
return ;
}
int idx=0;
for (int i=1;i<numsSize;i++){
if (nums[i]<nums[0]){
idx++;
int tmp=nums[idx];
nums[idx]=nums[i];
nums[i]=tmp;
}
}
int tmp=nums[0];
nums[0]=nums[idx];
nums[idx]=tmp;
quick(nums,idx);
quick(nums+idx+1,numsSize-1-idx);
}
int minDifference(int* nums, int numsSize) {
if (numsSize<=4){
return 0;
}
quick(nums,numsSize);
int res=nums[numsSize-4]-nums[0];
for (int i=1;i<=3;i++){
int tmp=nums[numsSize-4+i]-nums[i];
res=Min(res,tmp);
}
return res;
}