class Solution {
public:
int minDifference(vector<int>& nums) {
}
};
1509. 三次操作后最大值与最小值的最小差
给你一个数组 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原站题解
java 解法, 执行用时: 3 ms, 内存消耗: 54.9 MB, 提交时间: 2022-12-09 10:16:27
class Solution {
public int minDifference(int[] nums) {
int n = nums.length;
if (n <= 4) {
return 0;
}
int[] maxn = new int[4];
int[] minn = new int[4];
Arrays.fill(maxn, -1000000000);
Arrays.fill(minn, 1000000000);
for (int i = 0; i < n; i++) {
int add = 0;
while (add < 4 && maxn[add] > nums[i]) {
add++;
}
if (add < 4) {
for (int j = 3; j > add; j--) {
maxn[j] = maxn[j - 1];
}
maxn[add] = nums[i];
}
add = 0;
while (add < 4 && minn[add] < nums[i]) {
add++;
}
if (add < 4) {
for (int j = 3; j > add; j--) {
minn[j] = minn[j - 1];
}
minn[add] = nums[i];
}
}
int ret = Integer.MAX_VALUE;
for (int i = 0; i < 4; i++) {
ret = Math.min(ret, maxn[i] - minn[3 - i]);
}
return ret;
}
}
python3 解法, 执行用时: 180 ms, 内存消耗: 23 MB, 提交时间: 2022-12-09 10:15:41
class Solution:
def minDifference(self, nums: List[int]) -> int:
if len(nums) <= 4:
return 0
n = len(nums)
maxn = [-10**9] * 4
minn = [10**9] * 4
for i in range(n):
add = 0
while add < 4 and maxn[add] > nums[i]:
add += 1
if add < 4:
maxn[add:] = [nums[i]] + maxn[add:-1]
add = 0
while add < 4 and minn[add] < nums[i]:
add += 1
if add < 4:
minn[add:] = [nums[i]] + minn[add:-1]
ret = min(maxn[i] - minn[3 - i] for i in range(4))
return ret
golang 解法, 执行用时: 84 ms, 内存消耗: 8.2 MB, 提交时间: 2022-12-09 10:15:17
func minDifference(nums []int) int {
n := len(nums)
if n < 4 {
return 0
}
sort.Ints(nums)
ret := math.MaxInt32
for i := 0; i < 4; i++ {
if nums[n-4+i] - nums[i] < ret {
ret = nums[n-4+i] - nums[i]
}
}
return ret
}
java 解法, 执行用时: 17 ms, 内存消耗: 55.3 MB, 提交时间: 2022-12-09 10:09:46
class Solution {
public int minDifference(int[] nums) {
int n = nums.length;
if (n <= 4) {
return 0;
}
Arrays.sort(nums);
int ret = Integer.MAX_VALUE;
for (int i = 0; i < 4; i++) {
ret = Math.min(ret, nums[n - 4 + i] - nums[i]);
}
return ret;
}
}
python3 解法, 执行用时: 80 ms, 内存消耗: 23.6 MB, 提交时间: 2022-12-09 10:09:20
'''
直接对这个数组排序，即可直接得到其中最大的四个数与最小的四个数。
'''
class Solution:
def minDifference(self, nums: List[int]) -> int:
if len(nums) <= 4:
return 0
n = len(nums)
nums.sort()
ret = min(nums[n - 4 + i] - nums[i] for i in range(4))
return ret