2009. 使数组连续的最少操作数

题目描述

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

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

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

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

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

思路

一个简单的想法是先去重然后排序，这样只需要考虑有序数组的最小操作次数。

这里的有序数组是去重后排序的数组，连续数组是最终操作之后变得连续的数组。

那么怎样操作才能使操作次数最小呢？思考一下，数组中的数都有可能是最终的连续数组中的数字，既然这样，我们可以通过滑动窗口去寻找在连续数组范围里的数字。

举个例子，假设这个有序数组是 [1, 3, 5, 7, 8, 9, 11, 13]，它的长度是 8，假设 1 是连续数组中的最小值，那么最大值就只能是 8。那么我们可以去在有序数组中找比 8 大的数字，修改它们即可。假如 1 是最小值的话，那么我们需要修改 3 次。

对于其他数字也是一样，抽象一下，假设数组 A 的长度为 l，在我们遍历到 A 的第 i 个数字时，按照我们上面的算法，最大值应该是 A[i]+l-1。

那么我们就可以向右找到不大于 A[i]+l-1 的最大数字 A[j]，这样不需要修改的数字就是从 A[i] 到 A[j] 的一共 j-i+1 个数字，需要修改的和数字就是 l-(j-i+1) 个数字。

最终代码：

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        l = len(nums)
        sort_nums = sorted(set(nums))
        min_op = l
        j=0
        for i, left in enumerate(sort_nums):
            right = left+l-1
            while j < len(sort_nums) and sort_nums[j] <= right:
                j += 1
            min_op = min(l-(j-i), min_op)
        return min_op

想得太多

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        l = len(nums)
        sort_nums = sorted(set(nums))
        min_op = l
        for i, left in enumerate(sort_nums):
            right = left+l-1
            j = i+1
            while j < len(sort_nums) and sort_nums[j] <= right:
                j += 1
            min_op = min(l-(j-i), min_op)
        return min_op

这一份代码会 TLE，为什么？看一下官和官方答案的区别：

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        sortedUniqueNums = sorted((set(nums)))
        res = n
        j = 0
        for i, left in enumerate(sortedUniqueNums):
            right = left + n - 1
            while j < len(sortedUniqueNums) and sortedUniqueNums[j] <= right:
                res = min(res, n - (j - i + 1))
                j += 1
        return res

在官方的循环中没有在每次循环时给 j 赋值，而是随着 i 的增长，j 也在慢慢增长（而没有回溯），为什么可以这样做呢？好像还是蛮显然的，j 扩展到的位置表示之前的数字都在范围内，因此循环下一个 i 的时候范围不会变化，因此不需要回溯 j 了。

为了修改代码，我们把 j 的赋值挪到上面就行了：

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        l = len(nums)
        sort_nums = sorted(set(nums))
        min_op = l
        j=0
        for i, left in enumerate(sort_nums):
            right = left+l-1
            while j < len(sort_nums) and sort_nums[j] <= right:
                j += 1
            min_op = min(l-(j-i), min_op)
        return min_op

这样的话，之前的代码时间复杂度是 $O(n^2)$，而后面的代码时间复杂度只有 $O(n\log (n))$。