Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.169.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720018527.A.CAA.html
推 sustainer123: 大師