Leetcode-2009-使数组连续的最少操作数-c++

题目详见https://leetcode.cn/problems/minimum-number-of-operations-to-make-array-continuous/

官方题解

几个关键点

滑动窗口的单向性由sort()保证，既然已经排序了就只需要单向就可以等价双向。
题目中的连续和不连续这个称呼很巧妙，因为符合题目要求的数组sort之后一定是如123456之类的连续的数字，中间不会有空余，不信可以试一下。
依据上一点的内容，只要确定了最大值最小值，就只需要将其余的值换成他们之间不重复的数字就行了，比如最大值为7，最小值为1，就可以得到1*****7，*星号代表 $(1, 7)$ 这个开区间里面的任意整数。

在这里插入图片描述

debug🔧

按照官方样例：nums = [1,2,3,5,6]，执行完下列代码之后当前变量情况如下
在这里插入图片描述

int n = nums.size();
        unordered_set<int> cnt(nums.begin(), nums.end());
        vector<int> sortedUniqueNums(cnt.begin(), cnt.end());
        sort(sortedUniqueNums.begin(), sortedUniqueNums.end());
        int res = n, j = 0;

循环过程代码推导，只推导了一次for

在这里插入图片描述

注释代码

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> cnt(nums.begin(), nums.end());
        vector<int> sortedUniqueNums(cnt.begin(), cnt.end());
        sort(sortedUniqueNums.begin(), sortedUniqueNums.end());
        int res = n, j = 0;
        for(int i = 0; i < sortedUniqueNums.size(); i++){
            int right = sortedUniqueNums[i] + n - 1;
            while(j < sortedUniqueNums.size() && sortedUniqueNums[j] <= right){
                res = min(res, n - (j - i + 1));
                j++;
            }
        }
        return res;
    }
};