🔗 🟡 1509. Minimum Difference Between Largest and Smallest Value in Three Moves 1653

tags: `Biweekly Contest 30` `陣列(Array)` `排序(Sorting)` `貪心(Greedy)`

題意

給定一個整數陣列 $nums$ 。

在每次操作中，你可以選擇 $nums$ 中的任意一個元素並將其更改為任何值。

在最多進行 $3$ 次操作後，返回 $nums$ 中最大值和最小值之間的最小差。

約束條件

$1 \leq nums.length \leq 10^5$
$-10^9 \leq nums[i] \leq 10^9$

思路：排序(Sorting) + 貪心(Greedy)

在改變 $3$ 個數字後，會有 $n - 3$ 個數字不變。假設所有不變的數字範圍為 $[a, b]$ 。為了使最大值和最小值之間的差距最小，應將選擇的 $3$ 個數字改為 $[a, b]$ 中的任意 $3$ 個數字。故考慮剩餘 $n - 3$ 個數字的最大值和最小值差距 $b - a$ 即可。而為了使最大值和最小值之間的差距最小，選擇的數字應該是 $[a, b]$ 之外的數字，換句話說，會有至少連續 $n - 3$ 個數字落於 $[a, b]$ 之間。

故將 $nums$ 進行排序後，選擇連續的 $n-3$ 個數字，計算其最大值和最小值差距即可，總共只有 $4$ 種情況。

另外一種思路是從貪心的角度思考，為了使最大值和最小值之間的差距最小，改變的數字應該從最大和最小的 $3$ 個數字中選擇，因此可以選擇最小的 $k$ 個數字和最大的 $3-k$ 個數字，其中 $0 \leq k \leq 3$ ，總共有 $4$ 種情況，分別計算出來後取最小值即可。

以上兩種方式雖然思路不同，但操作上是一樣的。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ ，排序的時間複雜度。
空間複雜度： $\mathcal{O}(1)$ ，忽略排序的空間複雜度。

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 4:
            return 0
        nums.sort()
        k = n - 3 # 不變部分的數量
        ans = nums[-1] - nums[0]
        for i in range(n - k + 1):
            j = i + k - 1
            ans = min(ans, nums[j] - nums[i])
        return ans

class Solution {
public:
    int minDifference(vector<int>& nums) {
        int n = nums.size();
        if (n <= 4) return 0;
        sort(nums.begin(), nums.end());
        int k = n - 3;
        int ans = nums[n - 1] - nums[0];
        for (int i = 0; i <= n - k; i++) {
            int j = i + k - 1;
            ans = min(ans, nums[j] - nums[i]);
        }
        return ans;
    }
};