2024-06-03-荷兰国旗问题.md

发表于 | 分类于

题目描述

忙完出差的事情之后休整了一个周末，重新开始每日的算法复习。

在Top100里面选了这个题，LeetCode 75 颜色分类

这个题目对应的问题就是荷兰国旗问题。

荷兰国旗问题（Dutch National Flag Problem）是由计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）在1976年提出的一个经典算法问题。 这个问题描述了在一个数组中重排元素，以便将具有三种不同颜色的元素分开，类似于荷兰国旗的三条色带。具体问题如下：

假设你有一个包含红、白、蓝三种颜色的数组，目标是对这个数组进行排序，使得相同颜色的元素相邻，并且颜色的顺序为红、白、蓝。 可以将红、白、蓝分别用数字0、1、2表示，这样问题就转换为对一个只包含0、1、2的数组进行排序。

算法介绍

戴克斯特拉提出了一种线性时间复杂度 O(n) 的解决方法，通常称为“三路快排”或“荷兰国旗算法”。

算法基础思路是使用三个指针维护数组中的三个部分：

  • 小于1的部分
  • 等于1的部分
  • 大于1的部分

三个指针分别是：low，mid，high

起始状态：low=0，mid=0，high=array.length-1;

遍历数组比较，遍历条件是：mid没有超出数组的右边界：

  • 如果array[mid]==0,交换array[low]和array[mid]，同时low=low+1,mid=mid+1；
  • 如果array[mid]==1,mid=mid+1，循环下一个；
  • 如果array[high]==2,交换array[mid]和array[high]，high=high-1；

直到mid指向的位置移动到数组的末端

对应的人脑思路是这样的：

  • 从左往右遍历数组，始终认为mid指向数组中为1的部分;
  • 如果array[mid]==1，没有违背假设，往后推
  • 如果array[mid]==0,那么这个数字应该移动到左边，然后处理下一个
  • 如果array[mid]==2，那么这个数字应该移动到右边，然后处理下一个

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {

  public void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
      if (nums[mid] == 1) {
        mid++;
      } else if (nums[mid] == 0) {
        nums[mid] = nums[low];
        nums[low] = 0;
        mid++;
        low++;
      } else {
        nums[mid] = nums[high];
        nums[high] = 2;
        high--;
      }
    }
  }
}