Problem
You are given an integer array nums. In one move, you can choose one element of nums and change it by any value.
Return **the minimum difference between the largest and smallest value of nums after performing *at most three moves***.
Example 1:
Input: nums = [5,3,2,4]
Output: 0
Explanation: Change the array [5,3,2,4] to [2,2,2,2].
The difference between the maximum and minimum is 2-2 = 0.
Example 2:
Input: nums = [1,5,0,10,14]
Output: 1
Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1].
The difference between the maximum and minimum is 1-0 = 1.
Constraints:
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
Solution (Java)
class Solution {
public int minDifference(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int res = Integer.MAX_VALUE;
if (n < 4) {
return 0;
}
res = Math.min(res, nums[n - 4] - nums[0]);
res = Math.min(res, nums[n - 3] - nums[1]);
res = Math.min(res, nums[n - 2] - nums[2]);
res = Math.min(res, nums[n - 1] - nums[3]);
return res;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).