使数组连续的最少操作数
难度:
标签:
题目描述
代码结果
运行时间: 124 ms, 内存: 34.2 MB
// 思路：
// 1. 使用Java Stream对输入数组进行排序
// 2. 遍历排序后的数组，计算连续缺失的元素数量
// 3. 返回缺失的元素数量，即为最少操作次数
import java.util.Arrays;
public class Solution {
public int minOperations(int[] nums) {
nums = Arrays.stream(nums).sorted().toArray();
int n = nums.length;
int minOps = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int end = nums[i] + n - 1;
int count = (int) Arrays.stream(nums).filter(num -> num <= end).count();
minOps = Math.min(minOps, n - count);
}
return minOps;
}
}
解释
方法:
首先，将数组转换为集合并排序，以去除重复元素并获得所有唯一元素的有序列表。接着，使用滑动窗口的方法来找到最长的连续子数组，其长度最接近原数组长度。滑动窗口通过维护一个起点和一个终点来工作，开始时两者都在数组的起始位置。然后逐步向右移动终点，若当前窗口内的最大值与最小值之差大于或等于原数组的长度，则将起点右移，以尝试缩小窗口。操作的目标是使得窗口的大小尽可能接近原数组的长度。最后，由于需要将原数组变为连续数组，所以最少操作次数即为原数组的长度减去滑动窗口中得到的最大窗口长度。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在这种解法中需要将数组转换为集合并进行排序？
▷🦆
在滑动窗口算法中，如何确定何时右移窗口的起点left？
▷🦆
滑动窗口的最大长度是如何被计算出来的，具体是如何从代码中反映这一点的？
▷🦆
代码中`if a[i] - a[left] >= n: left += 1`这一行是基于什么逻辑？为什么选择这样的条件来移动左窗口？
▷