修改两个元素的最小分数
难度:
标签:
题目描述
You are given a 0-indexed integer array nums.
- The low score of
numsis the minimum value of|nums[i] - nums[j]|over all0 <= i < j < nums.length. - The high score of
numsis the maximum value of|nums[i] - nums[j]|over all0 <= i < j < nums.length. - The score of
numsis the sum of the high and low scores of nums.
To minimize the score of nums, we can change the value of at most two elements of nums.
Return the minimum possible score after changing the value of at most two elements of nums.
Note that |x| denotes the absolute value of x.
Example 1:
Input: nums = [1,4,3]
Output: 0
Explanation: Change value of nums[1] and nums[2] to 1 so that nums becomes [1,1,1]. Now, the value of |nums[i] - nums[j]| is always equal to 0, so we return 0 + 0 = 0.
Example 2:
Input: nums = [1,4,7,8,5] Output: 3 Explanation: Change nums[0] and nums[1] to be 6. Now nums becomes [6,6,7,8,5]. Our low score is achieved when i = 0 and j = 1, in which case |nums[i] - nums[j]| = |6 - 6| = 0. Our high score is achieved when i = 3 and j = 4, in which case |nums[i] - nums[j]| = |8 - 5| = 3. The sum of our high and low score is 3, which we can prove to be minimal.
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 109
代码结果
运行时间: 44 ms, 内存: 26.3 MB
/*
思路：
1. 使用Java Stream API进行排序和最大、最小值的计算。
2. 类似于Java版本的解法，通过修改最多两个元素来最小化得分。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int minScore(int[] nums) {
if (nums.length <= 2) return 0;
int n = nums.length;
List<Integer> sortedNums = Arrays.stream(nums).sorted().boxed().collect(Collectors.toList());
// 计算最小分数和
return IntStream.of(
sortedNums.get(n-1) - sortedNums.get(2),
sortedNums.get(n-2) - sortedNums.get(1),
sortedNums.get(n-3) - sortedNums.get(0),
sortedNums.get(n-1) - sortedNums.get(1)
).min().getAsInt();
}
}解释
方法:
此题解的总体思路是通过调整数组中的元素位置来尝试最小化数组的分数，分数定义为数组中最大差值与最小差值之和。首先，将数组排序，确保元素按升序排列。然后，选择可能的最小差值和最大差值组合，并比较它们的和。具体来说，考虑以下三种差值组合：1) 倒数第一和倒数第四的差，2) 倒数第三和第一个的差，3) 倒数第二和第二个的差。这些组合被选中是因为在修改最多两个元素的前提下，这些差值可能最小。最后，返回这三种组合中最小的和，作为最小化后的分数。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在选择差值组合时，考虑的是倒数第一和倒数第四的差、倒数第三和第一个的差、以及倒数第二和第二个的差？这样的组合如何确保能覆盖修改最多两个元素的场景？
▷🦆
在算法中，对于长度小于或等于3的数组，直接返回0的处理逻辑是基于什么考虑？为什么可以保证分数为0？
▷🦆
排序操作后直接选择特定的元素来计算差值是否总是有效的？这种方法是否考虑了所有可能的元素对以确保找到真正的最小和最大差值？
▷