Leetcode 颜色分类

这个算法采用了荷兰国旗问题（Dutch National Flag Problem）的解法思想，用三个指针将数组中的元素分为三个区域，并且对这些区域进行动态调整，达到排序的目的。

算法思想：

1. 三个指针：

   • low 指针表示当前0应该存放的区域的边界。
   • mid 指针用来遍历数组，每次检查当前位置的元素。
   • high 指针表示当前2应该存放的区域的边界。

2. 算法步骤：

   • 开始时，low 和 mid 都指向数组的开头，high 指向数组的末尾。
   • 遍历数组，当 mid 小于等于 high 时：
     • 如果 nums[mid] == 0，表示当前元素是红色（0），应该放到数组的前面，所以与 low 交换，low 和 mid 同时右移一位。
     • 如果 nums[mid] == 1，表示当前元素是白色（1），不需要移动，mid 右移一位。
     • 如果 nums[mid] == 2，表示当前元素是蓝色（2），应该放到数组的末尾，所以与 high 交换，并将 high 左移一位，而 mid 不动，等待交换后的元素检查。

3. 循环结束条件：

   • 当 mid 指针超过 high 时，说明所有的元素都已经按照红、白、蓝的顺序排列完毕。

关键点：

• in-place 排序：这个算法不需要额外的空间，直接在原数组上进行排序。
• 时间复杂度：每个元素最多被遍历一次，因此时间复杂度是 O(n)，其中 n 是数组的长度。
• 空间复杂度：由于只使用了常数级别的额外空间，空间复杂度为 O(1)。

例子：

假设输入数组是 [2,0,2,1,1,0]：

• 初始化 low = 0, mid = 0, high = 5。
• 第一次遍历 nums[mid] = 2，交换 nums[mid] 和 nums[high]，数组变为 [0,0,2,1,1,2]，high 左移。
• 第二次遍历 nums[mid] = 0，交换 nums[mid] 和 nums[low]，low 和 mid 右移，数组不变。
• 持续遍历并根据上述逻辑调整，最终数组为 [0,0,1,1,2,2]，排序完成。

这个算法的核心是通过遍历数组，动态调整0、1、2的位置，保证红色、白色、蓝色按照顺序排列。

java 代码：

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