Given an array with n objects colored red, white or blue, sort them in-place 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.
Example:
Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
思路：
fb的高频题，边界处理很容易出bug，要小心
扫一遍，maintain四个区域，
0 0 | 1 1 | XXXX |2 2 [0, zero) = 0 [zero, i) = 1 [i, two] = unchecked elements (two, len-1] = 2
代码：
1 /** 2 0 0 | 1 | xxx | 2 3 4 if x == 1: 5 0 0 | 1 | 1 xx | 2 6 ^ 7 0 0 | 1 | 1 xx | 2 8 ^ 9 10 if x == 2: 11 0 0 | 1 | 2xx | 2 12 ^i ^two 13 0 0 | 1 | x x 2| 2 14 ^i ^two 15 16 if x == 0: 17 0 0 | 1 | 0 xx | 2 18 ^zero ^i 19 0 0 | 0 | 1 xx | 2 20 ^i 21 **/ 22 23 class Solution { 24 public void sortColors(int[] nums) { 25 // corner 26 if(nums == null || nums.length == 0) return ; 27 28 int zero = -1; // nums[0...zero] = 0 29 int two = nums.length; // nums[two...nums.length-1] = 2 30 int i = 0; 31 32 while(i < two){ 33 if(nums[i] == 1){ 34 i++; 35 }else if(nums[i] == 2){ 36 two--; // to reserve a room 37 swap(nums, i , two); 38 }else{ // nums[i] == 0 39 zero++; // to reserve a room 40 swap(nums, i , zero); 41 i++; 42 } 43 } 44 } 45 private void swap(int[] nums, int a, int b){ 46 int temp = nums[a]; 47 nums[a] = nums[b]; 48 nums[b] = temp; 49 } 50 }
转载于:https://www.cnblogs.com/liuliu5151/p/9070189.html
相关资源：数据结构—成绩单生成器