[LeetCode]75. Sort Colorsjava

/**75. Sort Colors * @param nums * red,white,blue,不能使用常规排序 */ public void sortColors0(int[] nums) { int red = -1, white = -1, blue = -1; for (int i = 0; i < nums.length; i++) { if (nums[i] == 0) { red++; } else if (nums[i] == 1) { white++; } else if (nums[i] == 2) { blue++; } } for (int i = 0; i < nums.length; i++) { if (red >= 0) { nums[i] = 0; red--; } else if (white >= 0) { nums[i] = 1; white--; } else if (blue >= 0) { nums[i] = 2; blue--; } } }

//统计个数,之后再次赋值

改进：利用双指针移动

public void sortColors(int[] nums) { int red = 0; int blue = nums.length-1; for (int i = 0; i < blue+1; ) {//循环条件i<blue+1 if (nums[i] == 0) { int temp = nums[red]; nums[red] = nums[i]; nums[i] = temp; ++red; ++i; } else if (nums[i] == 2) { int temp = nums[blue]; nums[blue] = nums[i]; nums[i] = temp; --blue;//注意i不变，交换后继续处理nums[i] } else { ++i; } } }

red和blue分别指向头0，和尾length-1 遍历数组： 发现[i]=0，交换[i]和[red] 发现[i]=2，交换[i]和[blue]