Leetcode-1509. 三次操作后最大值与最小值的最小差
程序员文章站
2022-03-01 14:58:44
...
链接
题目
给你一个数组 nums ,每次操作你可以选择 nums 中的任意一个元素并将它改成任意值。
请你返回三次操作后, nums 中最大值与最小值的差的最小值。
示例
示例 1:
输入:nums = [5,3,2,4]
输出:0
解释:将数组 [5,3,2,4] 变成 [2,2,2,2].
最大值与最小值的差为 2-2 = 0 。示例 2:
输入:nums = [1,5,0,10,14]
输出:1
解释:将数组 [1,5,0,10,14] 变成 [1,1,0,1,1] 。
最大值与最小值的差为 1-0 = 1 。示例 3:
输入:nums = [6,6,0,1,1,4,6]
输出:2示例 4:
输入:nums = [1,5,6,14,15]
输出:1
说明
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
思路
参考谭光志
由于是求最大值与最小值的最小差值,所以要尽量让最大值和最小值接近,首先需要对数组进行排序。
1 2 3 4 5 6 7 8 9 10
用上面的例子来做参考:
- 如果不能修改值,直接用最大值减去最小值就是结果
10 - 1
- 如果能修改一个值,就有两种可能:
10 - 2(修改N[0])
9 - 1(修改N[n-1])
- 如果能修改两个值,就有三种可能:
10 - 3(修改N[0]和N[1])
9 - 2(修改N[0]和N[N-1])
8 - 1(修改N[n-1]和N[n-2])
- 如果能修改三个值,就有四种可能:
10 - 4(修改N[0]、N[1]、N[2])
9 - 3(N[0]、N[1]、N[n-1])
8 - 2(N[0]、N[n-1]、N[n-2])
7 - 1(N[n-1]、N[n-2]、N[n-3])
比较所有的可能值,取其中最小的值就是结果。
C++ Code
class Solution {
public:
int minDifference(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
if (n <= 4) return 0;
return min({nums[n-1] - nums[3], nums[n-2] - nums[2], nums[n-3] - nums[1], nums[n-4] - nums[0]});
}
};
上一篇: 4.18 Object类的使用