颜色分类
- leetcode - 75. 颜色分类
- 题目描述
- 双指针
- 代码演示
- 双指针算法专题
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. 供暖器