稀碎从零算法笔记Day43-LeetCode:使数组连续的最少操作数

题型：数组、滑动窗口、贪心

链接：2009. 使数组连续的最少操作数 - 力扣（LeetCode）

来源：LeetCode

题目描述

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

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

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

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

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

题目样例

题目思路

将滑动窗口设为数组长度 n，区间为【left,left+n-1】，记录不在区间内的数组的个数，每次以最大的值来更新

C++代码

class Solution {
public:
    int minOperations(vector<int>& nums) {
        // 数组长度前后不变： left = right + 1 - n
        // nums的元素个数 n  大小在区间内的元素个数 k 那么剩下的元素(需要操作的)个数：n - k
        
        // 核心：确定left——以一个数当left的标:看k够不够大 滑动窗口为:[left,left + n]
        int n = nums.size();
                    // 排序
                    // sort(nums.begin(),nums.end());
        // 去重
        unordered_set<int> tempset(nums.begin(),nums.end());
        vector<int> numsTemp(tempset.begin(),tempset.end());
        // 排序
        sort(numsTemp.begin(),numsTemp.end());
        // numsTemp是nums的排序+去重版本
        int len = numsTemp.size();
        // ans记录n-k
        // 每新遍历一个数，就更新ans，从n开始
        int ans = n,right = 0;
        for(int left=0;left<len;left++)
        {
            int target = numsTemp[left] + n - 1;//有了判断标准
            while(right < len && numsTemp[right] <= target)
            {
                // 满足条件是k++，k = j - i + k
                ans = min(ans,n - (right - left + 1));
                ++right;
            }
        }
    // 答案是n - k
    return ans;
    }
};

结算页面