vvrf / DSA.log

问题拆解

数组里只有 0、1、2 三种值，原地排序，题目进一步要求只扫一遍。

值域只有三个，计数排序显然可行：数一遍各有几个，再回填一遍——两趟，O(1) 空间，但不满足“一趟扫描”的进阶要求。

一趟做完的思路是维护三个区域的边界，这就是 Dijkstra 提出的荷兰国旗划分：low 左边全是 0，high 右边全是 2，i 是当前检查位置，i 与 low 之间全是 1。不变式是 [0, low) 为 0、[low, i) 为 1、(high, n) 为 2，[i, high] 是未检查区。i 每看一个数：是 0 就和 low 换、两者齐进；是 1 直接过；是 2 就和 high 换、只收缩 high。当 i 越过 high，未检查区清空，排序完成。

循环不变式是这类指针题的地基：先写清每个区间装什么，指针怎么动就只是“维持不变式”的机械推论。

荷兰国旗三指针划分

public void sortColors(int[] nums) {
    int low = 0, i = 0, high = nums.length - 1;
    while (i <= high) {
        if (nums[i] == 0) {
            swap(nums, i, low);
            low++;
            i++; // low 换来的只能是 1（或就是自己），可以放行
        } else if (nums[i] == 2) {
            swap(nums, i, high);
            high--; // 换来的数未检查，i 原地不动
        } else {
            i++;
        }
    }
}

private void swap(int[] nums, int a, int b) {
    int t = nums[a];
    nums[a] = nums[b];
    nums[b] = t;
}

def sortColors(nums: List[int]) -> None:
    low, i, high = 0, 0, len(nums) - 1

    while i <= high:
        if nums[i] == 0:
            nums[i], nums[low] = nums[low], nums[i]
            low += 1
            i += 1  # low 换来的只能是 1（或就是自己），可以放行
        elif nums[i] == 2:
            nums[i], nums[high] = nums[high], nums[i]
            high -= 1  # 换来的数未检查，i 原地不动
        else:
            i += 1

func sortColors(nums []int) {
    low, i, high := 0, 0, len(nums)-1
    for i <= high {
        switch nums[i] {
        case 0:
            nums[i], nums[low] = nums[low], nums[i]
            low++
            i++ // low 换来的只能是 1（或就是自己），可以放行
        case 2:
            nums[i], nums[high] = nums[high], nums[i]
            high-- // 换来的数未检查，i 原地不动
        default:
            i++
        }
    }
}

pub fn sort_colors(nums: &mut Vec<i32>) {
    let (mut low, mut i) = (0usize, 0usize);
    let mut high = nums.len() - 1;
    while i <= high {
        match nums[i] {
            0 => {
                nums.swap(i, low);
                low += 1;
                i += 1; // low 换来的只能是 1（或就是自己），可以放行
            }
            2 => {
                nums.swap(i, high);
                if high == 0 {
                    break; // 防止 usize 减到负数
                }
                high -= 1; // 换来的数未检查，i 原地不动
            }
            _ => i += 1,
        }
    }
}

全题最容易错的一行就是和 high 交换后的处理：换回来的数来自未检查区，可能是 0、1、2 中任何一个，所以 i 必须原地再看一次；如果习惯性地 i++，[1, 2, 0] 这样的用例里 0 会被留在 2 的位置上。而和 low 交换后 i 可以放心前进——low 位于已检查区，那里要么是 i 自己（low == i 时），要么是一个被验过的 1，换过来不需要重查。这个不对称正是三指针的精髓。

循环条件是 i <= high 而不是 i < high：i == high 时那个位置还没检查过，提前退出就漏了它。Rust 版额外防了一手 high 为 0 时的 usize 下溢。

复杂度

指标	复杂度	原因
时间	`O(n)`	每轮要么 i 前进，要么 high 后退，未检查区严格缩小
空间	`O(1)`	原地交换，只有三个指针

可以迁移的模式

三向切分是快速排序处理大量重复元素的核心优化（three-way partition），骨架一模一样；
交换类双指针的通用心法：换来的元素属于哪个区，决定指针要不要停下来重查；
动手前先写下循环不变式，指针移动的每条规则都应该能从不变式推出来。

“交换之后这个位置的数查过没有”——原地划分类题目的 bug 十有八九出在这一问上。