排序题目：三次操作后最大值与最小值的最小差

题目

标题和出处

标题：三次操作后最大值与最小值的最小差

出处：1509. 三次操作后最大值与最小值的最小差

难度

5 级

题目描述

要求

给定一个数组 $\text{nums}$，每次操作可以选择 $\text{nums}$ 中的任意一个元素并将其改成任意值。

返回三次操作后 $\text{nums}$ 中最大值与最小值的差的最小值。

示例

示例 1：

输入：$\text{nums = [5,3,2,4]}$
输出：$\text{0}$
解释：将数组 $\text{[5,3,2,4]}$ 变成 $\text{[2,2,2,2]}$。最大值与最小值的差为 $\text{2}-\text{2}=\text{0}$。

示例 2：

输入：$\text{nums = [1,5,0,10,14]}$
输出：$\text{1}$
解释：将数组 $\text{[1,5,0,10,14]}$ 变成 $\text{[1,1,0,1,1]}$。最大值与最小值的差为 $\text{1}-\text{0}=\text{1}$。

数据范围

• $\text{1}\le \text{nums.length}\le {\text{10}}^{\text{5}}$
• ${\text{-10}}^{\text{9}}\le \text{nums[i]}\le {\text{10}}^{\text{9}}$

解法一

思路和算法

如果数组的长度不大于 $4$，则经过最多三次操作之后一定可以使数组中的所有元素相等，此时最小的差是 $0$。

如果数组的长度大于 $4$，则将数组升序排序之后，对最小的 $x$ 个数和最大的 $y$ 个数操作可以使得差最小，其中 $x$ 和 $y$ 都是非负整数，$x+y=3$。

用 $n$ 表示数组 $\text{nums}$ 的长度，用 $i$ 和 $j$ 分别表示有序数组中的第 $x+1$ 小的数和第 $y+1$ 大的数所在下标，则有 $i=x$，$j=n-y-1$，根据 $x+y=3$ 可得 $j-i=n-4$。将最小的 $x$ 个元素改成 $\text{nums}[i]$ 并将最大的 $y$ 个元素改成 $\text{nums}[j]$，则操作之后的最大值是 $\text{nums}[j]$，最小值是 $\text{nums}[i]$，最大值与最小值的差是 $\text{nums}[j]-\text{nums}[i]$。

如果操作的元素不是最小的 $x$ 个元素和最大的 $y$ 个元素，则操作之后一定存在小于等于 $\text{nums}[i]$ 的值或大于等于 $\text{nums}[j]$ 的值，最大值与最小值的差一定不会小于 $\text{nums}[j]-\text{nums}[i]$。因此为了使最大值与最小值的差最小，应该操作最小的 $x$ 个元素和最大的 $y$ 个元素。

遍历所有满足 $0\le i,j<n$ 且 $j-i=n-4$ 的下标对 $(i,j)$，计算每个下标对的 $\text{nums}[j]-\text{nums}[i]$，其中的最小差值即为三次操作后 $\text{nums}$ 中最大值与最小值的差的最小值。

代码

class Solution {public int minDifference(int[] nums) {int n = nums.length;if (n <= 4) {return 0;}Arrays.sort(nums);int minDiff = nums[n - 1] - nums[0];for (int i = 0, j = n - 4; j < n; i++, j++) {minDiff = Math.min(minDiff, nums[j] - nums[i]);}return minDiff;}
}

复杂度分析

• 时间复杂度：$O(n\log n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。排序需要 $O(n\log n)$ 的时间，排序后需要遍历数组中的四个下标对，遍历的时间是 $O(1)$，时间复杂度是 $O(n\log n)$。

• 空间复杂度：$O(\log n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。排序需要 $O(\log n)$ 的递归调用栈空间。

解法二

思路和算法

根据解法一可知，只需要维护数组 $\text{nums}$ 中最大的四个元素与最小的四个元素，即可得到最大值与最小值的最小差值。因此，可以在不排序的情况下遍历数组得到最大的四个元素与最小的四个元素，然后计算最大值与最小值的最小差值。

维护两个长度为 $4$ 的数组 $\text{maxVals}$ 和 $\text{minVals}$ 分别用于存储最大的四个元素与最小的四个元素，初始时 $\text{maxVals}$ 的元素值都是 $-\infty$，$\text{minVals}$ 的元素值都是 $+\infty$。遍历数组 $\text{nums}$ 的过程中更新 $\text{maxVals}$ 和 $\text{minVals}$，并保持 $\text{maxVals}$ 单调递减和 $\text{minVals}$ 单调递增。

遍历数组 $\text{nums}$ 结束之后，对于 $0\le i<4$ 的每个下标 $i$ 计算 $\text{maxVals}[i]-\text{minVals}[3-i]$，其中的最小值即为三次操作后 $\text{nums}$ 中最大值与最小值的最小差值。

代码

class Solution {public int minDifference(int[] nums) {int n = nums.length;if (n <= 4) {return 0;}int[] maxVals = new int[4];int[] minVals = new int[4];Arrays.fill(maxVals, Integer.MIN_VALUE);Arrays.fill(minVals, Integer.MAX_VALUE);for (int num : nums) {int maxIndex = 0;while (maxIndex < 4 && num <= maxVals[maxIndex]) {maxIndex++;}if (maxIndex < 4) {for (int i = 2; i >= maxIndex; i--) {maxVals[i + 1] = maxVals[i];}maxVals[maxIndex] = num;}int minIndex = 0;while (minIndex < 4 && num >= minVals[minIndex]) {minIndex++;}if (minIndex < 4) {for (int i = 2; i >= minIndex; i--) {minVals[i + 1] = minVals[i];}minVals[minIndex] = num;}}int minDiff = Integer.MAX_VALUE;for (int i = 0; i < 4; i++) {minDiff = Math.min(minDiff, maxVals[i] - minVals[3 - i]);}return minDiff;}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。遍历数组需要 $O(n)$ 的时间，由于只需要维护四个最大元素和四个最小元素，因此每个元素更新最大与最小元素的时间都是 $O(1)$。

• 空间复杂度：$O(1)$。由于只需要维护四个最大元素和四个最小元素，因此空间复杂度是 $O(1)$。