LeetCode 题解工作台
使数组连续的最少操作数
给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。 如果 nums 满足以下条件，那么它是 连续的 ： nums 中所有元素都是 互不相同 的。 nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。 比方说， nums…
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们先将数组排序，去重。 然后遍历数组，枚举以当前元素 作为连续数组的最小值，通过二分查找找到第一个大于 $nums[i] + n - 1$ 的位置 ，那么 就是当前元素作为最小值时，连续数组的长度，更新答案，即 $ans = \min(ans, n - (j - i))$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 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 <= 1051 <= nums[i] <= 109
解题思路
方法一：排序 + 去重 + 二分查找
我们先将数组排序，去重。
然后遍历数组，枚举以当前元素 作为连续数组的最小值，通过二分查找找到第一个大于 的位置 ，那么 就是当前元素作为最小值时，连续数组的长度，更新答案，即 。
最后返回 即可。
时间复杂度 ，空间复杂度 。其中 为数组长度。
class Solution:
def minOperations(self, nums: List[int]) -> int:
ans = n = len(nums)
nums = sorted(set(nums))
for i, v in enumerate(nums):
j = bisect_right(nums, v + n - 1)
ans = min(ans, n - (j - i))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \cdot \log{}n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
The candidate understands the need for sorting before applying any further optimizations.
- question_mark
The candidate efficiently identifies the correct subarray using sliding window logic.
- question_mark
The candidate uses hash tables effectively to minimize operations and detect gaps.
常见陷阱
外企场景- error
Failing to sort the array initially, leading to unnecessary complexity in gap detection.
- error
Misunderstanding the sliding window approach and applying it incorrectly, resulting in higher complexity.
- error
Not considering the impact of large array sizes and struggling with time and space constraints.
进阶变体
外企场景- arrow_right_alt
What if the array contains only a single element? The problem becomes trivial as no operations are needed.
- arrow_right_alt
What if the array is already sorted or already continuous? The result will be 0 operations required.
- arrow_right_alt
If the array contains duplicate elements, they can still be part of the solution if they fit into the continuous subarray.