Skip to content

Latest commit

 

History

History
184 lines (135 loc) · 5.63 KB

README.md

File metadata and controls

184 lines (135 loc) · 5.63 KB
comments difficulty edit_url rating source tags
true
中等
1608
第 98 场双周赛 Q2
贪心
数组
排序

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$ 的长度。

相似题目：

Python3

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])

Java

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));
    }
}

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]});
    }
};

Go

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]))
}

TypeScript

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]);
}

Rust

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])
    }
}

C

#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]));
}