Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
一刷
题解：two pointer
注意事项
- 循环条件 index<=right, 如果是遍历的话，index>right之后会把1和2又交换回来。
- index++的情况是nums[index] == 0 或者nums[index] == 1，nums[index] == 2就不进行index++，因为交换过来的值不一定为1，要进行下一步的判断。
public class Solution {
public void sortColors(int[] nums) {
if(nums == null || nums.length == 0) return;
int first = 0, last = nums.length-1, index = 0;
while(index<=last){
if(nums[index] == 0){
swap(nums, index, first++);
index++;
}
else if(nums[index] == 2){
swap(nums, index, last--);
}
else index++;
}
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
二刷
题解：双指针，记得在while循环的时候i的限制条件。避免使用无效的swap， 比如位置0和0 swap
public class Solution {
public void sortColors(int[] nums) {
sort(nums, nums.length);
}
private void sort(int[] nums, int n){
int second = n-1, zero = 0;
for(int i=0; i<=second; i++){
while(nums[i] == 2 && i<second) swap(i, second--, nums);
while(nums[i] == 0 && i>zero) swap(i, zero++, nums);
}
}
private void swap(int i, int j, int[] nums){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
