Loomione

荷兰国旗问题

 
  • Jun 10, 2024

荷兰国旗问题

采用三个指针将数组中的 0、1 和 2 分别放到数组的左侧、中间和右侧。

循环不变量

在进入循环之前和每次循环迭代之后，以下三个循环不变量必须成立：

  1. 左侧区域全为 0：所有索引小于 left 的位置都为 0。
  2. 中间区域全为 1：所有索引从 left 到 i-1 的位置都为 1。
  3. 右侧区域全为 2：所有索引大于 right 的位置都为 2。

这些循环不变量的正式描述如下：

  • 对于所有 k，其中 0 <= k < left，有 nums[k] == 0。
  • 对于所有 k，其中 left <= k < i，有 nums[k] == 1。
  • 对于所有 k，其中 right < k < n，有 nums[k] == 2。

初始化

在开始时，left = 0，i = 0，right = nums.size() - 1。初始化时，数组的所有元素还未处理，因此这些循环不变量自然成立：

  • 左侧区域为空（left = 0）。
  • 中间区域为空（i = 0）。
  • 右侧区域为空（right = nums.size() - 1）。

维持循环不变量

我们需要检查每次循环迭代中这些不变量是否保持不变：

  1. 当 nums[i] == 2 时：
    • 交换 nums[i] 和 nums[right]，然后 right--。
    • 此时，由于交换后的 nums[right+1] 是原来的 nums[i]（等于 2），所以将它移到右侧区域。
    • i 不动，因为交换后的新元素可能是 0 或 1，需要重新检查。
    • 因此，右侧区域依然全为 2，左侧和中间区域不变，循环不变量依旧成立。
  2. 当 nums[i] == 0 时：
    • 交换 nums[i] 和 nums[left]，然后 left++ 和 i++。
    • 此时，交换后的 nums[left-1] 是原来的 nums[i]（等于 0），所以将它移到左侧区域。
    • 此时，交换后的 nums[i-1] 是原来的 nums[left]（等于 0），因为 nums[i-1] 已经被检查过(等于1)，所以 i 可以增加。
    • 左侧区域全为 0，右侧区域不变，中间区域由 left 到 i-1 全为 1，循环不变量依旧成立。
  3. 当 nums[i] == 1 时：
    • 仅增加 i。
    • 中间区域由 left 到 i-1 全为 1，左侧和右侧区域不变，循环不变量依旧成立。

终止

当 i > right 时，循环终止。此时：

  • 左侧区域全为 0。
  • 中间区域全为 1。
  • 右侧区域全为 2。

因此，数组 nums 被正确排序，证明算法正确。

代码实现

void sortColors(vector<int>& nums) {
    int left = 0, i = 0, right = nums.size() - 1;
    while (i <= right) {
        if (nums[i] == 2) {
            swap(nums[right--], nums[i]);
        } else if (nums[i] == 0) {
            swap(nums[left++], nums[i++]);
        } else {
            i++;
        }
    }
}

这个算法在每次迭代中维持循环不变量，并且在终止时数组按预期排序。时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

Search