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

本文主要是介绍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;}
};