题目描述:
标签:数组 双指针 排序
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
代码:
思路分析:
其实这题最暴力的算法就是直接用api排序QAQ。不过真的太简单粗暴了。
这题主要是想考察快排的思想。比某个数小的在左边,等于某个数的在中间,大于某个数的在右边。还主要考察了“循环不变量”的思想。
1、要划分为三个区间
[0,zero)对应0
[zero,i)对应1
[two,len-1]对应2
所以需要定义三个指针zero,i(也就是one),two分别对应着0区间的右边界、1区间的右边界、2区间的左边界。可见从这个区间定义知道当i==two的时候循环停止。
2、为了保证初始化的时候 [0, zero) 为空,设置 zero = 0,所以要先交换再加加
3、为了保证初始化的时候 [two, len - 1] 为空,设置 two = len,所以要先减减再交换
class Solution { public void sortColors(int[] nums) { int len = nums.length; if(len < 2){ return; } int zero = 0; int i = 0; int two = len; while(i < two){ if(nums[i] == 0){ swap(nums,i,zero); i++; zero++; }else if(nums[i] == 1){ i++; }else{ two--; swap(nums,i,two); } } } public void swap(int[] nums,int index1,int index2){ int tmp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = tmp; } }