2567.修改两个元素的最小分数:三种情况(也可O(n))

【LetMeFly】2567.修改两个元素的最小分数:三种情况(也可O(n))

力扣题目链接:https://leetcode.cn/problems/minimum-score-by-changing-two-elements/

给你一个下标从 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$。

其实也就三种改法:

  1. 修改最大的两个数:把这两个数变小,最大的数变成原本第三大的数,最小的数还是原本最小的数
  2. 修改最小的两个数:把这两个数变大,最大的数还是原本最大的数,最小的数变成原本第三小的数
  3. 修改最大和最小的两个数:最大数变小最小数变大,最大的数是原本第二大的数,最小的数是原本第二小的数

返回以上三种修改方法得到的最大数和最小数之差中最小的那个。

时空复杂度

  • 时间复杂度$O(n\log n)$
  • 空间复杂度$O(\log n)$

由于只需要确定最大值、第二大值、第三大值、最小值、第二小值、第三小值,所以其实也可以使用几个变量一次遍历得出,这样则有:

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
* @LastEditTime: 2026-11-19 22:29:22
*/
class Solution {
public:
int minimizeSum(vector<int>& nums) {
ranges::sort(nums);
int n = nums.size();
return min(
nums[n - 3] - nums[0], min( // 改最大的两个
nums[n - 1] - nums[2], // 改最小的两个
nums[n - 2] - nums[1] // 改最小和最大的那两个
)
);
}
};

End

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


2567.修改两个元素的最小分数:三种情况(也可O(n))
https://blog.letmefly.xyz/2026/11/20/LeetCode 2567.修改两个元素的最小分数/
作者
发布于
2026年11月20日
许可协议