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;
}