数据结构与算法 / 系统课时

原地交换处理数组位置约束

原地交换处理数组位置约束

当数组中的有效值可以映射到固定索引时,哈希表并不是唯一选择。把值直接交换到它应该出现的位置,可以在原数组中完成“值到位置”的索引化。本节用缺失正数问题掌握归位条件、重复值保护和线性复杂度证明。

学习目标

  • 识别“值域可以映射到数组下标”的原地归位题型
  • 写出不会因重复元素陷入死循环的交换条件
  • 理解多次 while 交换为什么整体仍然是线性复杂度

把数组本身当作位置表

以“寻找第一个缺失的正整数”为例。长度为 n 的数组如果答案不超过 n,那么值 x 最理想的位置就是下标 x - 1:值 1 放在位置 0,值 2 放在位置 1,以此类推。

因此只需要关心 [1, n] 范围内的值。负数、0 以及大于 n 的数都不可能占据答案对应的位置,可以留在原处。完成归位后,从左向右找到第一个满足 nums[i] != i + 1 的位置,答案就是 i + 1;如果全部匹配,则答案为 n + 1。

原地交换归位过程

这种思路常被称为原地归位、索引放置或 cyclic placement。关键前提不是题目名字,而是有效值与有限索引之间存在直接映射。

交换直到当前位置无法继续归位

一个位置经过交换后会得到新的值,因此不能只用一次 if。只要当前位置的新值仍属于 [1, n],并且它还没有位于自己的目标位置,就继续交换。

同时必须检查目标位置是否已经存放相同值。假设数组中有两个 2,而索引 1 已经是 2,如果仍继续交换两个相同的值,数组不会发生变化,while 就会永久循环。

下面的完整程序求第一个缺失正整数,并在运行后打印归位后的数组。

python
from typing import List


def first_missing_positive(nums: List[int]) -> int:
    n = len(nums)

    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            # 当前值 x 应被放到索引 x - 1;交换后继续检查 nums[i] 的新值
            target = nums[i] - 1
            nums[i], nums[target] = nums[target], nums[i]

    for i, value in enumerate(nums):
        if value != i + 1:
            return i + 1

    return n + 1


if __name__ == "__main__":
    data = [3, 4, -1, 1]
    print(first_missing_positive(data))
    print(data)

预期输出

text
2
[1, -1, 3, 4]

值 1、3、4 都已经回到对应位置,而索引 1 上不是期望值 2,所以第一个缺失正整数是 2。

为什么嵌套循环仍然是线性的

代码外层有 for,内部还有 while,但不能仅凭语法结构判断为平方复杂度。每次真正发生交换时,都会把一个处于有效值域且尚未归位的值送到它的目标位置。这样的成功归位次数受到数组长度限制,不可能无限增长。

因此所有位置累计执行的有效交换是 O(n)O(n),随后再扫描一次也是 O(n)O(n),总时间复杂度仍为 O(n)O(n)。算法只使用几个临时变量,额外空间复杂度为 O(1)O(1)。

什么时候可以使用原地归位

遇到“缺失值、重复值、值是否出现”一类数组题时,可以先检查三个条件:有效值域是否与数组长度同阶、每个有效值能否唯一映射到某个索引、题目是否允许修改输入数组。三个条件同时满足时,原地归位往往能替代额外哈希表。

如果必须保留原数组顺序、输入不可修改,或者值域巨大且无法压缩到数组索引范围,就不应强行使用交换归位。真正的识别信号是“值本身可以指出它应该待在哪个位置”,而不是看到缺失数字就机械套模板。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

原地交换处理数组位置约束

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通