使数组连续的最少操作数

难度: Hard

给你一个整数数组 nums 。每一次操作中，你可以将 nums 中任意一个元素替换成任意整数。

如果 nums 满足以下条件，那么它是 连续的 ：

nums 中所有元素都是 互不相同 的。
nums 中最大元素与最小元素的差等于 nums.length - 1 。

比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。

请你返回使 nums 连续的最少操作次数。

示例 1：

输入：nums = [4,2,5,3]
输出：0
解释：nums 已经是连续的了。

示例 2：

输入：nums = [1,2,3,5,6]
输出：1
解释：一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ，是连续数组。

示例 3：

输入：nums = [1,10,100,1000]
输出：3
解释：一个可能的解是：
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ，是连续数组。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Submission

运行时间: 124 ms

内存: 34.2 MB

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        a = sorted(set(nums))
        m, left = len(a), 0
        for i in range(m):
            if a[i] - a[left] >= n: left += 1
        return n - (m - left)

Explain

首先，将数组转换为集合并排序，以去除重复元素并获得所有唯一元素的有序列表。接着，使用滑动窗口的方法来找到最长的连续子数组，其长度最接近原数组长度。滑动窗口通过维护一个起点和一个终点来工作，开始时两者都在数组的起始位置。然后逐步向右移动终点，若当前窗口内的最大值与最小值之差大于或等于原数组的长度，则将起点右移，以尝试缩小窗口。操作的目标是使得窗口的大小尽可能接近原数组的长度。最后，由于需要将原数组变为连续数组，所以最少操作次数即为原数组的长度减去滑动窗口中得到的最大窗口长度。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)  # 原数组的长度
        a = sorted(set(nums))  # 去重并排序
        m, left = len(a), 0  # m 是去重后数组的长度，left 是滑动窗口的起始位置
        for i in range(m):
            if a[i] - a[left] >= n: left += 1  # 如果窗口内最大值与最小值之差大于等于 n，移动窗口起点
        return n - (m - left)  # 返回原数组长度减去最大连续子数组长度

Explore

将数组转换为集合的目的是去除数组中的重复元素，因为重复的元素在寻找最长连续子数组时不会提供额外的帮助，且会导致统计上的误差。排序则是为了方便后续通过比较元素的差值来快速判断元素间是否连续，同时也便于使用滑动窗口技术来寻找最长的连续子序列。

在滑动窗口算法中，窗口的起点left被右移的条件是当前窗口内的元素（从起点left到终点i的元素）已不能构成连续序列。具体来说，当窗口内的最大值与最小值之差大于或等于数组长度n时，说明窗口内不能只通过增加元素就能构成连续数组，因此需要通过移动起点left来尝试缩小这一差值，使窗口内的元素可能构成连续序列。

滑动窗口的最大长度是通过遍历去重并排序后的数组，同时调整窗口的起点和终点来计算的。在代码中，这一点体现在通过不断移动终点i（for循环的迭代变量），并在必要时调整起点left（if语句内的条件判断和操作），来尝试找到最大的滑动窗口长度。最终，最大的滑动窗口长度计算为`m - left`，其中m是去重排序后数组的长度。

代码中的这一行逻辑是基于需要保持窗口内元素可以构成连续序列的考虑。当窗口内的最大元素和最小元素之间的差大于或等于n时，窗口内元素的数量已经不可能通过简单地添加缺失的元素来达到n个连续的整数（这意味着窗口内存在过大的间隙）。因此，需要通过移动窗口的左边界left来尝试减小这个差值，目的是缩小窗口直到窗口内的元素可以构成一个几乎完整的连续序列。这样做可以使得最终的操作次数（添加或移动元素）最小化。