千问 LeetCode 2009.使数组连续的最少操作数 Python3实现

以下是 LeetCode 2009. 使数组连续的最少操作数 的 Python3 实现，采用 去重 + 排序 + 滑动窗口（双指针） 的高效方法：

✅ 解题思路回顾

目标：将数组变为一个长度为 n 的连续整数序列（如 [x, x+1, ..., x+n-1]），求最少修改次数。

关键观察：
- 最终序列有 n 个互不相同的连续整数。
- 我们希望保留尽可能多的原数组中的不同元素，且这些元素能落在某个长度为 n 的区间内。
- 因此：
最少操作数 = n - 最多可保留的不同元素个数

步骤：
1. 去重并排序（重复元素无法同时保留）。
2. 使用滑动窗口（双指针） 找出最长子数组，使得 arr[right] - arr[left] int:
n = len(nums)
# Step 1: 去重并排序
arr = sorted(set(nums))
m = len(arr)

max_keep = 1 # 至少可以保留一个数
left = 0

# Step 2: 双指针滑动窗口
for right in range(m):
# 缩小窗口直到 arr[right] - arr[left] = n:
left += 1
# 当前窗口 [left, right] 内的元素都可以保留
max_keep = max(max_keep, right - left + 1)

return n - max_keep

📊 复杂度分析

- 时间复杂度：
- 去重：O(n)
- 排序：O(m log m)，其中 m ≤ n
- 双指针遍历：O(m)（每个元素最多进/出窗口一次）
→ 总体 O(n log n)

- 空间复杂度：O(n)（存储去重后的列表）

🧪 示例验证

示例 1：
nums = [4, 2, 5, 3]
去重排序后: [2,3,4,5]
窗口 [2,5]: 5-2=3 4 → 最大窗口长度=1 → 操作数=4-1=3

🔁 补充：二分查找版本（也可行）

如果你偏好二分，也可以对每个 left 用 bisect_right 找右边界：

import bisect

class Solution:
def minOperations(self, nums: List[int]) -> int:
n = len(nums)
arr = sorted(set(nums))
m = len(arr)
max_keep = 0

for i, val in enumerate(arr):
# 目标区间: [val, val + n - 1]
right_bound = val + n - 1
# 找第一个 > right_bound 的位置
j = bisect.bisect_right(arr, right_bound)
max_keep = max(max_keep, j - i)

return n - max_keep

但双指针版本更高效（O(m) vs O(m log m)），且代码简洁。

✅ 推荐使用双指针滑动窗口版本，清晰、高效、易理解。