博文中会简要介绍Leetcode P0075题目分析及解题思路。
“Sort Colors”是一道比较有意思的题目，这道题的难点主要在于follow-up中要求只扫一遍就更新整个数组。
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]Follow up:
- A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.- Could you come up with a one-pass algorithm using only constant space?
类似的这类题目其实用到了一种特殊的排序方法，即彩虹排序（Rainbow Sort）。交换两个指针指向的元素就像用一道彩虹连接这两个指针然后交换彩虹两端指向的元素一样，又由于这种交换是用在排序上，故得名“彩虹排序”。
具体思路已经在代码中注释。简单来说就是利用两个变量来记录位置，一个变量指向当前左起第一个非0位置，第二个变量指向当前左起第一个非1（且非0）位置，然后根据当前遍历指针指向的元素，若为0则与非0位置（不为默认值）交换，若为1则与非1位置交换。以此类推，遍历一遍即可。
以下是Java的题解代码实现。
class Solution {
public void sortColors(int[] nums) {
if (nums == null || nums.length == 0)
return;
// leftNonZero即L0记录左边第一个非0位置，同理leftNonOne即L1记录左边第一个非1位置
// right即遍历数组的指针
int leftNonZero = -1, leftNonOne = -1, right = 0;
while (right < nums.length) {
switch (nums[right]) {
case 0:
// 若有非0位置，则交换，
// 可能会与1交换，所以right不动，可以再判断当前right
if (leftNonZero != -1) {
nums[right] = nums[leftNonZero];
nums[leftNonZero] = 0;
// 如果L0和L1相同，则都要右移
if (leftNonZero == leftNonOne) {
++leftNonOne;
}
++leftNonZero;
}
else
++right;
break;
case 1:
// 若非0位置为默认值，则更新
leftNonZero = (leftNonZero == -1)? right: leftNonZero;
// 若有非1位置，则交换
if (leftNonOne != -1) {
nums[right] = nums[leftNonOne];
nums[leftNonOne] = 1;
++leftNonOne;
}
++right;
break;
default:
// 更新非0位置和非1位置
leftNonZero = (leftNonZero == -1)? right: leftNonZero;
leftNonOne = (leftNonOne == -1)? right: leftNonOne;
++right;
break;
}
}
}
}
上述解法是将0和1往前移动，所以记录的是第一个非0和第一个非1（且非0）的位置。其实这道题还可以将1和2往后移，思路上基本是一致的，通过记录当前遍历到的范围内，第一个1的位置和第一个2的位置来辅助交换。
以下是Java的题解代码实现。
class Solution {
public void sortColors(int[] nums) {
// 向后交换
// 在当前遍历到的范围内，l0指向第一个1的位置，l1指向第一个2的位置。
int l0 = -1, l1 = -1, right = 0;
while (right < nums.length) {
int num = nums[right];
switch (num) {
case 0: {
// 这里提前break是因为和0交换位置的是l0指针，即1与0交换了位置，所以后续仍要进入nums[right]=1的条件部分，所以此时right指针无需后移。
if (l0 != -1) {
nums[l0] = nums[right];
nums[right] = 1;
++l0;
break;
}
if (l1 != -1) {
nums[l1] = nums[right];
nums[right] = 2;
++l1;
}
++right;
break;
}
case 1: {
if (l1 == -1) {
l0 = (l0 == -1)? right: l0;
}
else {
nums[l1] = nums[right];
nums[right] = 2;
l0 = (l0 == -1)? l1: l0;
++l1;
}
++right;
break;
}
default: {
l1 = (l1 == -1)? right: l1;
++right;
break;
}
}
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
void sortColors(vector<int>& nums) {
if (nums.size() == 0)
return;
int leftNonZero = -1, leftNonOne = -1, right = 0;
while (right < nums.size()) {
switch (nums[right]) {
case 0:
if (leftNonZero != -1) {
nums[right] = nums[leftNonZero];
nums[leftNonZero] = 0;
// 如果L0和L1相同，则都要右移
if (leftNonZero == leftNonOne) {
++leftNonOne;
}
++leftNonZero;
}
else
++right;
break;
case 1:
leftNonZero = (leftNonZero == -1)? right: leftNonZero;
if (leftNonOne != -1) {
nums[right] = nums[leftNonOne];
nums[leftNonOne] = 1;
++leftNonOne;
}
++right;
break;
default:
leftNonZero = (leftNonZero == -1)? right: leftNonZero;
leftNonOne = (leftNonOne == -1)? right: leftNonOne;
++right;
break;
}
}
}
};