class Solution {
public:
int smallestRangeII(vector<int>& nums, int k) {
}
};
910. 最小差值 II
给你一个整数数组 nums，和一个整数 k 。
对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。
nums 的 分数 是 nums 中最大元素和最小元素的差值。
在更改每个下标对应的值之后，返回 nums 的最小 分数 。
示例 1：
输入：nums = [1], k = 0 输出：0 解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。
示例 2：
输入：nums = [0,10], k = 2 输出：6 解释：将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。
示例 3：
输入：nums = [1,3,6], k = 3 输出：3 解释：将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。
提示：
1 <= nums.length <= 1040 <= nums[i] <= 1040 <= k <= 104原站题解
javascript 解法, 执行用时: 20 ms, 内存消耗: 51.6 MB, 提交时间: 2024-10-21 09:18:47
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var smallestRangeII = function(nums, k) {
nums.sort((a, b) => a - b);
const n = nums.length;
let ans = nums[n - 1] - nums[0];
for (let i = 1; i < n; i++) {
const mx = Math.max(nums[i - 1] + k, nums[n - 1] - k);
const mn = Math.min(nums[0] + k, nums[i] - k);
ans = Math.min(ans, mx - mn);
}
return ans;
};
php 解法, 执行用时: 44 ms, 内存消耗: 20.6 MB, 提交时间: 2023-10-08 15:30:49
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function smallestRangeII($nums, $k) {
$n = count($nums);
sort($nums);
$ans = $nums[$n-1] - $nums[0];
for ( $i = 1; $i < $n; $i++ ) {
$y = max($nums[$n-1] - $k, $nums[$i-1] + $k);
$x = min($nums[0] + $k, $nums[$i] - $k);
$ans = min($y - $x, $ans);
}
return $ans;
}
}
cpp 解法, 执行用时: 20 ms, 内存消耗: 15.4 MB, 提交时间: 2023-10-08 15:28:14
class Solution {
public:
int smallestRangeII(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int res = nums.back() - nums[0];
int n = nums.size();
for (int i = 0; i < n-1; ++i) {
int l = min(nums[0]+k, nums[i+1]-k);
int h = max(nums[n-1]-k, nums[i]+k);
res = min(res, h-l);
}
return res;
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 42.9 MB, 提交时间: 2023-10-08 15:27:44
class Solution {
public int smallestRangeII(int[] A, int K) {
int N = A.length;
Arrays.sort(A);
int ans = A[N-1] - A[0];
for (int i = 0; i < A.length - 1; ++i) {
int a = A[i], b = A[i+1];
int high = Math.max(A[N-1] - K, a + K);
int low = Math.min(A[0] + K, b - K);
ans = Math.min(ans, high - low);
}
return ans;
}
}
rust 解法, 执行用时: 8 ms, 内存消耗: 2.3 MB, 提交时间: 2023-10-08 15:27:21
impl Solution {
pub fn smallest_range_ii(a: Vec<i32>, k: i32) -> i32 {
use std::cmp::{min,max};
let mut a_mux = a;
a_mux.sort();
let len = a_mux.len();
let mut ans = a_mux[len - 1] - a_mux[0];
for i in 0..len - 1 {
let high = max(a_mux[len - 1] - k,a_mux[i] + k);
let low = min(a_mux[0] + k,a_mux[i + 1] - k);
ans = min(ans,high - low);
}
ans
}
}
python3 解法, 执行用时: 88 ms, 内存消耗: 16.9 MB, 提交时间: 2023-10-08 15:25:43
class Solution:
def smallestRangeII(self, nums: List[int], k: int) -> int:
nums.sort()
ret = nums[-1] - nums[0]
for i in range(1, len(nums)):
minnum = min(nums[0] + k, nums[i] - k)
maxnum = max(nums[i-1] + k, nums[-1] - k)
ret = min(ret, maxnum - minnum)
return ret
golang 解法, 执行用时: 20 ms, 内存消耗: 5.9 MB, 提交时间: 2023-10-08 15:25:10
func smallestRangeII(nums []int, k int) int {
sort.Slice(nums, func(i, j int) bool { // 先按从小到大排序
return nums[i] < nums[j]
})
n := len(nums)
res := nums[n-1] - nums[0] // 最大与最小的差值
for i := 1; i < n; i++ {
x := min(nums[0] + k, nums[i] - k) // 最小值
y := max(nums[n-1] - k, nums[i-1] + k) // 最大值
res = min(y-x, res)
}
return res
}
func max(a, b int) int{ if a > b { return a }; return b }
func min(a, b int) int{ if a < b { return a }; return b }