优化最小正缺失整数数组操作至O(n²)以下，及k+1次操作后数组求解

一、时间复杂度优化方案（降至O(n)） #

原算法每次操作需遍历最后k个元素查找最小缺失正整数，最坏时间复杂度为O(nk)（当k≈n时即为O(n²)）。要优化到O(n²)以下，可通过滑动窗口+哈希集合+跟踪候选值实现线性时间复杂度：

• 初始化阶段：
  • 遍历初始数组（长度k），将所有正整数存入哈希集合，同时从1开始找到第一个不在集合中的数，记为current_m（即第一次要添加的元素）。
• 每次操作步骤：
  1. 将current_m追加到数组末尾。
  2. 更新滑动窗口的集合：移除当前窗口中被挤出的元素（即数组中第len(array)-k-1个元素，若为正整数则从集合中删除），并将新添加的current_m加入集合（若为正整数）。
  3. 更新current_m：如果current_m存在于更新后的集合中，就不断递增它，直到找到第一个不在集合中的正整数。

哈希集合的增删查操作平均耗时O(1)，且current_m的总递增次数不会超过n（最多添加n个元素），因此整体时间复杂度为O(n)，远低于O(n²)。

二、执行k+1次操作后的最终数组 #

执行k+1次操作后，最终数组由初始k个元素和1到k+1的一个排列拼接而成。

推导依据： #

1. 任意k个元素的窗口，其最小缺失正整数必然在[1, k+1]范围内：若1_{k都在窗口中，最小缺失为k+1；否则是1}k中第一个未出现的数。
2. 假设存在某个x ∈ {1,2,...,k+1}从未被添加，意味着x在所有k+1个窗口中都存在。但k+1个连续的k长度窗口，覆盖的数组范围是从第0位到第2k位（总长度2k+1），x要同时出现在所有窗口中会导致位置矛盾（既得在初始数组的前k位，又得在后续添加的元素位，不可能实现）。因此每个x ∈ {1,2,...,k+1}都会被恰好添加一次，形成1到k+1的一个排列。

内容的提问来源于stack exchange，提问作者ArashJafariyan