2567-修改两个元素的最小分数
给你一个下标从 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
下午两点【biIibiIi@灵茶山艾府】直播讲题,记得关注哦~
根据题意,修改成 nums 中的数字,可以让最小得分为 0。那么分数就等于最大得分。
那么从小到大排序后,我们可以:
- 修改最大的两个数为 nums}[n-3],最大得分为 nums}[n-3]-\textit{nums}[0];
- 修改最小的为 nums}[1],最大的为 nums}[n-2],最大得分为 nums}[n-2]-\textit{nums}[1];
- 修改最小的两个数为 nums}[2],最大得分为 nums}[n-1]-\textit{nums}[2]。
这样修改的理由是,修改成再更大/更小的数,不会影响最大得分了。
1 | class Solution: |
1 | func minimizeSum(a []int) int { |
复杂度分析
- 时间复杂度:O(n\log n),其中 n 为 nums 的长度。手动维护或者用快速选择可以做到 O(n)。
- 空间复杂度:O(1)。忽略排序时栈的开销,仅用到若干额外变量。
Comments