### 主要收获 2

Two Pointers这类问题的关键之一是：要明确指针的责任。不要跳来跳去。比如这题，lt表示<target的数的边界，gt表示>target的数的边界，那么在每次迭代的时候就一定要保证他们确实尽到他们的职责。

### 题目

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.

### Three Way Partition问题

[0, 1, 2, 2, 2, 0, 0, 1]


[0, 0, 0, 1, 1, 2, 2, 2]


#### 代码

• firstEqual指向第一个=target的数的位置。（没有就为-1
• firstGreater指向第一个>target的数的位置。（没有就为-1

public class Solution {
public void sortColors(int[] colors) {
threeWayPartition(colors,1);
}
public void threeWayPartition(int[] nums, int target) {
int firstEqual = -1, firstGreater = -1; //维护两个指向三区块间边界的指针
for (int i = 0; i < nums.length; i++) {
if (firstGreater < 0 && nums[i] > target) {
firstGreater = i; continue;
}
if (nums[i] == target) {
if (firstGreater >= 0) {
exchange(nums,firstGreater,i);
if (firstEqual < 0) { firstEqual = firstGreater; }
firstGreater++;
} else if (firstEqual < 0){
firstEqual = i;
}
}
if (nums[i] < target) {
int tempCursor = i; // 标明需要交换的位置
if (firstGreater >= 0) {
exchange(nums,firstGreater,tempCursor);
tempCursor = firstGreater;
firstGreater++;
}
if (firstEqual >= 0) {
exchange(nums,firstEqual,tempCursor);
firstEqual++;
}
}
}
}
public void exchange(int[] nums, int first, int second) {
int temp = nums[first];
nums[first] = nums[second];
nums[second] = temp;
}
}


### 标准Three Way Partition, 数组分两头维护

1. lt指向最后一个确定< target的数。
2. gt指向第一个确定> target的数。
3. ilt之间是= target的数。
4. igt之间是还没有遍历到的数。

lt初始化位置在左端0.gt初始位置在右端length-1。当igt交叉的时候，结束迭代。

#### 代码

public void threeWayPartition(int[] nums, int target) {
int lessThan = 0, greaterThan = nums.length-1, cursor = lessThan + 1;
while (cursor <= greaterThan) {
if (nums[cursor] < target) {
exchange(nums,lessThan++,cursor);
if (lessThan >= cursor) { cursor++; } // 注意这步，和下面简化版的区别
} else if (nums[cursor] > target) {
exchange(nums,greaterThan--,cursor);
} else {
cursor++;
}
}
}


#### 简化版

public class Solution {
public void sortColors(int[] colors) {
threeWayPartition(colors,1);
}
public void threeWayPartition(int[] nums, int target) {
int lessThan = 0, greaterThan = nums.length-1, cursor = lessThan + 1;
while (cursor <= greaterThan) {
if (nums[cursor] < target) {
exchange(nums,++lessThan,cursor++); // 简化在这里，因为不论有没有等于target的数，这里cursor都是加1的。
} else if (nums[cursor] > target) {
exchange(nums,--greaterThan,cursor);
} else {
cursor++;
}
}
}
public void exchange(int[] nums, int first, int second) {
int temp = nums[first];
nums[first] = nums[second];
nums[second] = temp;
}
}


### 红白蓝，专供版

#### 代码

public class Solution {
public void sortColors(int[] nums) {
int zero = 0, two = nums.length-1, cursor = 0;
while (cursor <= two) {
switch (nums[cursor]) {
case 0:
exchange(nums,zero++,cursor++); break;
case 1:
cursor++; break;
case 2:
exchange(nums,cursor,two--); break;
}
}
}
public void exchange(int[] nums, int first, int second) {
int temp = nums[first];
nums[first] = nums[second];
nums[second] = temp;
}
}