leetcode2009--使数组连续的最少操作数

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

1. 题意

给定一个数组，求最少的操作数使得数组连续。

每次操作你可选择一个数，将它变为任意其他数。

leetcode2009

2. 题解

思路：反向考虑，最多能保留多少个数字使得当前数组连续。

就变成了$[x,x+sz-1]$的滑动窗口，最多包含了几个数组中的数字。

还有需要去重，重复的数字一定需要一次来改变。

最后的答案即$sz-max\_number\_in\_window$

其中有序数组去重对应leetcode26–删除有序数组重复项。

2.1 排序+去重+滑动窗口

class Solution {
public:int minOperations(vector<int>& nums) {sort(nums.begin(), nums.end());int sz = nums.size();int cnt = 0;for (int i = 1; i < sz; ++i) {if ( nums[i] != nums[cnt]) {nums[++cnt] = nums[i];}}cout << cnt  + 1<< endl;int l = 0;int ans = 0;for (int i = 1; i < cnt + 1; ++i) {if ( nums[i] - nums[l] > sz - 1) {ans = max(ans, i - l);while (i < cnt + 1 && nums[i] - nums[l] > sz - 1)++l;}}ans = max(ans, cnt + 1 - l);return sz - ans;}
};

2.2 排序+去重+二分

可以固定左边界，二分寻找右边界。

class Solution {
public:int minOperations(vector<int>& nums) {sort(nums.begin(), nums.end());int sz = nums.size();int cnt = 0;for (int i = 1; i < sz; ++i) {if ( nums[i] != nums[cnt]) {nums[++cnt] = nums[i];}}int l = 0;int ans = sz;for (int i = 0; i < cnt + 1; ++i) {int l = i + 1;int r = cnt + 1;while ( l < r) {int m = l + (r -l >> 1);if ( nums[m] - nums[i] <= sz - 1) {l = m + 1;}else {r = m;}}ans = min(ans, sz -(l - i));}return ans;}
};

这篇关于leetcode2009--使数组连续的最少操作数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---