LeetCode 使数组连续的最少操作数

本文主要是介绍LeetCode 使数组连续的最少操作数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

地址：. - 力扣（LeetCode）
难度：困难
题目描述：给你一个整数数组 nums 。每一次操作中，你可以将 nums 中任意一个元素替换成 **任意 **整数。
如果 nums 满足以下条件，那么它是 连续的 ：

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

比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。
请你返回使 nums 连续的最少操作次数。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109

题解过程

条件1：互不相同，

所以得把相同的数替换掉，并且替换的数不能是数组中存在的数

条件2：最大的元素与最小的元素差 === nums.length（n） - 1

如何确定最大值最小值？
假设最小值为 left最大值，那么最大值 right = left+n−1。

问：假设最大最小值确定，那么相同需要替换的数字需要替换成什么？替换的数字可能因为存在数组中又导致重复吗？

答：这种情况是肯定不会存在的，因为最大值-最小值 === n - 1
也就是说最大值和最小值直接就差值了n-1，假设数组紧密排列，两项之间只差值1，得到的数组会是[1,2,3……n]，刚好满足最大值 - 最小值 === n-1

反向考虑，假设最后连续的数组的最小值为 left，则最大值 right=left+n−1。
原数组 nums 中，如果有位于 [left,right]中的，如果只出现一次，我们可以对其进行保留；
多次出现时，我们则需要对其进行操作；
不在这个区间的数字，我们也需要对其进行操作，将它们变成其他数字来对这个区间进行补足。
因此，我们需要统计原数组 nums中，位于区间 [left,right]内不同的数字个数 k，而 n−k就是我们需要进行的操作数。

接下来就是需要确定 left，我们可以将原数组 nums所有不同的数字作为 left的候选值，分别计算出 n−k，然后求出最小值。

这样的话，我们可以先将原数组进行去重后排序，然后利用滑动窗口。
滑动窗口左端点的值作为 left，然后向右扩展右端点，窗口的长度即为 k，求出所有可能性下最小的 n−k即可。

例子：[4,2,2,5,3]

例子：[1,10,100,1000]

/*** @param {number[]} nums* @return {number}*/
var minOperations = function(nums) {const n = nums.length;// 去重const sortedUniqueNums = [...new Set(nums)];// 排序sortedUniqueNums.sort((a, b) => a - b);let res = n;let j = 0;for (let i = 0; i < sortedUniqueNums.length; i++) {const left = sortedUniqueNums[i]; // 最小值const right = left + n - 1; // 最大值while (j < sortedUniqueNums.length && sortedUniqueNums[j] <= right) {// 因为排序过 所以后面的都是不符合要求的 //为什么去重不影响结果？ 因为n是没去重的结果，减去的是符合要求的数，所以最终结果是对的// （i-1）是小于left的值  所以符合要求的结果是j-(i-1) = j-i+1res = Math.min(res, n - (j - i + 1));j++;}}return res;};