# 2009. 使数组连续的最少操作数
### 题目地址(2009. 使数组连续的最少操作数)
### 题目描述
```
给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。
如果 nums 满足以下条件，那么它是 连续的 ：
nums 中所有元素都是 互不相同 的。
nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。
比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。
请你返回使 nums 连续 的 最少 操作次数。
示例 1：
输入：nums = [4,2,5,3]
输出：0
解释：nums 已经是连续的了。
示例 2：
输入：nums = [1,2,3,5,6]
输出：1
解释：一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ，是连续数组。
示例 3：
输入：nums = [1,10,100,1000]
输出：3
解释：一个可能的解是：
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ，是连续数组。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 109
```
### 前置知识
* 二分
### 公司
* 暂无
### 思路
由于最终的数组长度一定是原数组长度。 因此题目让我们找最少操作数，其实等价于找最多保留多少个数不变，这样我们就可以通过最少的操作数使得数组连续。
朴素的思路是枚举所有的区间 \[a,b] 其中 a 和 b 为区间 \[min(nums),max(nums)] 中的两个数。这种思路的时间复杂度是 $O(v^2)$，其中 v 为 nums 的值域。看一下数据范围，很明显会超时。
假设我们最终形成的连续区间是 \[l, r]，那么 nums\[i] 一定有一个是在端点的，因为如果都不在端点，变成在端点不会使得答案更差。这样我们可以枚举 nums\[i] 作为 l 或者 r，分别判断在这种情况下我们可以保留的数字个数最多是多少。
为了减少时间复杂度，我们可以先对数组排序，这样就可以二分找答案，使得时间复杂度降低。看下时间复杂度排序的时间是可以允许的，因此这种解决可以 ac。
具体地：
* 对数组去重
* 对数组排序
* 遍历 nums，对于每一个 num 我们需要找到其作为左端点时，那么右端点就是 v + on - 1，于是我们在这个数组中找值在 num 和 v + on - 1 的有多少个，这些都是可以保留的。剩下的我们需要通过替换得到。 num 作为右端点也是同理。这两种我们需要找最优的。所有 i 的最优解就是答案。
具体参考下方代码。
### 关键点
* 反向思考，题目要找最少操作数，其实就是找最多保留多少个数
* 对于每一个 num 我们需要找到其作为左端点时，那么右端点就是 v + on - 1，于是我们在这个数组中找值在 num 和 v + on - 1 的有多少个，这些都是可以保留的
* 排序 + 二分 减少时间复杂度
### 代码
* 语言支持：Python3
Python3 Code:
```python
import bisect
class Solution:
def minOperations(self, nums: List[int]) -> int:
ans = on = len(nums)
nums = list(set(nums))
nums.sort()
n = len(nums)
for i, v in enumerate(nums):
# nums[i] 一定有一个是在端点的，如果都不在端点，变成在端点不会使得答案更差
r = bisect.bisect_right(nums, v + on - 1) # 枚举 i 作为左端点
l = bisect.bisect_left(nums, v - on + 1) # 枚举 i 作为右端点
ans = min(ans, n - (r - i), n - (i - l + 1))
return ans + (on - n)
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(nlogn)$
* 空间复杂度：$O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/2009.minimum-number-of-operations-to-make-array-continuous.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.