leetcode - 75. 颜色分类

难度 - 中等
原题链接 - 颜色分类

题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]

提示：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

双指针

该题为经典的荷兰国旗问题，由于题目本质是要我们将数分成三段。
具体步骤：
我们用L 和 R 卡住左边和边，左边放0，右边放1，中间位置放1，
遍历到0时放在左边，指针向右移动，继续比较
碰到1时，什么都不用做，继续向右比较，
碰到2时，放到右边。这样下来就分成了三层。
一次遍历就完成了。

代码演示

/** 
*分层
*/
public void sortColors(int[] nums) {//左边界，最开始左边没数据，用-1位置代替int l = -1;//右边没数据，初始化为数组长度int r = nums.length;//指针位置，比较int index = 0;while(index < r){if(nums[index] == 0){swap(nums,++l,index++);}else if(nums[index] == 1){index++;}else{swap(nums,index,--r);}}}//交换的方法void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}

双指针算法专题

leetcode870. 优势洗牌

leetcode 881. 救生艇

leetcode 475. 供暖器