LeetCode 75. Sort Colors
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?
解析：
此题目为排序问题，对于不同颜色的物体，根据红、白、蓝进行排序，要求原地处理。
解法1:
根据提示中的信息，先统计不同颜色物体的数量，然后根据每种颜色的数量进行赋值。
具体代码如下：
[cc lang=”C++”]
class Solution {
public:
void sortColors(vector
vector
for(int num : nums)
colors[num]++;
for(int i=0,cur=0; i < 3; i++)
{
for(int j=0; j < colors[i]; j++)
nums[cur++] = i;
}
}
};
[/cc]
解法2:
题目中要求只遍历一次数组，采用双指针法，red指向开头位置，blue指向结束位置。遍历每个元素，如果为0则与red交换，并将red指针后移一位，遇到2则与blue交换，并将blue指针前移一位，如果为1则继续。实现置换后0在前，2在后，中间的为1.
具体代码如下：
[cc lang="C++"]
class Solution {
public:
void sortColors(vector
int red = 0, blue = nums.size()-1;
for(int i=0; i <= blue; i++)
{
if(nums[i] == 0)
swap(nums[i], nums[red++]);
else if(nums[i] == 2)
swap(nums[i--], nums[blue--]);//此处i--为了抵消循环的i++,即blue置换过来的元素还有可能需要置换
}
}
};
[/cc]
About Author
