Question

2567. 修改两个元素的最小分数

English Version

题目描述

给你一个下标从 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 <= 105
• 1 <= nums[i] <= 109

解法

方法一：排序 + 贪心

根据题意我们知道，最小得分实际上是排序数组相邻两个元素的最小差值，最大得分是排序数组首尾元素的差值。数组 $nums$ 的分数是最小得分与最大得分的和。

因此，我们可以先对数组进行排序。由于题目允许我们修改数组中最多两个元素的值，我们可以通过修改一个数，让其跟数组中的另一个数相同，使得最小得分为 $0$，那么数组 $nums$ 的分数实际上就是最大得分。我们可以选择进行如下修改之一：

1. 修改最小的两个数为 $nums[2]$，那么最大得分为 $nums[n - 1] - nums[2]$；
2. 修改最小的一个数为 $nums[1]$，最大的一个数为 $nums[n - 2]$，那么最大得分为 $nums[n - 2] - nums[1]$；
3. 修改最大的两个数为 $nums[n - 3]$，那么最大得分为 $nums[n - 3] - nums[0]$。

最后，我们返回上述三种修改的得分的最小值即可。

时间复杂度 $O(n \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组 $nums$ 的长度。

相似题目：

• 1509. 三次操作后最大值与最小值的最小差

class Solution:
  def minimizeSum(self, nums: List[int]) -> int:
    nums.sort()
    return min(nums[-1] - nums[2], nums[-2] - nums[1], nums[-3] - nums[0])

class Solution {
  public int minimizeSum(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int a = nums[n - 1] - nums[2];
    int b = nums[n - 2] - nums[1];
    int c = nums[n - 3] - nums[0];
    return Math.min(a, Math.min(b, c));
  }
}

class Solution {
public:
  int minimizeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    return min({nums[n - 1] - nums[2], nums[n - 2] - nums[1], nums[n - 3] - nums[0]});
  }
};

func minimizeSum(nums []int) int {
  sort.Ints(nums)
  n := len(nums)
  return min(nums[n-1]-nums[2], min(nums[n-2]-nums[1], nums[n-3]-nums[0]))
}

function minimizeSum(nums: number[]): number {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  return Math.min(nums[n - 3] - nums[0], nums[n - 2] - nums[1], nums[n - 1] - nums[2]);
}

impl Solution {
  pub fn minimize_sum(mut nums: Vec<i32>) -> i32 {
    nums.sort();
    let n = nums.len();
    (nums[n - 1] - nums[2]).min(nums[n - 2] - nums[1]).min(nums[n - 3] - nums[0])
  }
}

#define min(a, b) (((a) < (b)) ? (a) : (b))

int cmp(const void* a, const void* b) {
  return *(int*) a - *(int*) b;
}

int minimizeSum(int* nums, int numsSize) {
  qsort(nums, numsSize, sizeof(int), cmp);
  return min(nums[numsSize - 1] - nums[2], min(nums[numsSize - 2] - nums[1], nums[numsSize - 3] - nums[0]));
}