修改两个元素的最小分数

难度: Medium

给你一个下标从 0 开始的整数数组 nums 。

nums 的最小得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最小值。
nums的最大得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最大值。
nums 的分数是最大得分与最小得分的和。

我们的目标是最小化 nums 的分数。你最多可以修改 nums 中 2 个元素的值。

请你返回修改 nums 中 至多两个 元素的值后，可以得到的 最小分数 。

|x| 表示 x 的绝对值。

示例 1：

输入：nums = [1,4,3]
输出：0
解释：将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。|nums[i] - nums[j]| 的值永远为 0 ，所以我们返回 0 + 0 = 0 。

示例 2：

输入：nums = [1,4,7,8,5]
输出：3
解释：
将 nums[0] 和 nums[1] 的值变为 6 ，nums 变为 [6,6,7,8,5] 。
最小得分是 i = 0 且 j = 1 时得到的 |nums[i] - nums[j]| = |6 - 6| = 0 。
最大得分是 i = 3 且 j = 4 时得到的 |nums[i] - nums[j]| = |8 - 5| = 3 。
最大得分与最小得分之和为 3 。这是最优答案。

提示：

3 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Submission

运行时间: 44 ms

内存: 26.3 MB

class Solution:
    def minimizeSum(self, nums: List[int]) -> int:
        if len(nums) <= 3:
            return 0
        list1 = sorted(nums)
        list2 = []
        list2.append(list1[-1] - list1[2])
        list2.append(list1[-3] - list1[0])
        list2.append(list1[-2] - list1[1])
        list3 = sorted(list2)
        return list3[0]

Explain

此题解的总体思路是通过调整数组中的元素位置来尝试最小化数组的分数，分数定义为数组中最大差值与最小差值之和。首先，将数组排序，确保元素按升序排列。然后，选择可能的最小差值和最大差值组合，并比较它们的和。具体来说，考虑以下三种差值组合：1) 倒数第一和倒数第四的差，2) 倒数第三和第一个的差，3) 倒数第二和第二个的差。这些组合被选中是因为在修改最多两个元素的前提下，这些差值可能最小。最后，返回这三种组合中最小的和，作为最小化后的分数。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minimizeSum(self, nums: List[int]) -> int:
        if len(nums) <= 3:
            return 0  # 若数组长度小于或等于3，任何修改都能使得分数为0
        list1 = sorted(nums)  # 对数组进行排序
        list2 = []
        # 计算三种差值组合
        list2.append(list1[-1] - list1[2])  # 最大元素与第四大的差
        list2.append(list1[-3] - list1[0])  # 第三大元素与最小的差
        list2.append(list1[-2] - list1[1])  # 第二大元素与第二小的差
        list3 = sorted(list2)  # 对这三个差值进行排序
        return list3[0]  # 返回最小的组合差值

Explore

在选择这些特定的差值组合时，目的是尽可能地最小化数组的最小得分和最大得分的和，同时确保在修改最多两个元素的情况下仍能达到这一目的。倒数第一和第四的差值考虑的是在极端情况下（即除了最大值和次最大值外的情况），最大值可能会被修改，而影响到最大差值。倒数第三和第一个的差值则考虑了最小值可能被修改的情况。倒数第二和第二个的差值则是在一种比较均衡的情况下考虑两端值的变化。这三种组合通过覆盖数组排序后的关键位置，使得即使在修改了最多两个元素的情况下，也能较好地估计并尝试最小化最大差值和最小差值的和。

当数组长度小于或等于3时，可以通过修改至多两个元素使得所有元素相等。例如，对于三个元素的数组，可以选择将两个元素修改为与第三个元素相同的值，这样数组中任意两个元素之间的差都将为0。因此，最小差值和最大差值都为0，它们的和自然也为0。这是一个基于数组长度特性的特殊情况处理，可以简化计算并直接得出结果。

排序后直接选择特定元素来计算差值的方法在大多数情况下是有效的，因为排序可以帮助我们快速定位到潜在的最大差值和最小差值。特别是在目标是找到修改最多两个元素后的最小分数时，这种方法通过选取关键位置上的元素进行差值计算，可以有效地近似实际的最小和最大差值。然而，这种方法虽然在大部分情况下是足够的，但它确实没有考虑所有可能的元素对。在特定情况下，可能需要更详尽的检查来确保找到真正的最小和最大差值，特别是在更复杂的修改策略或其他约束条件存在时。