[LeetCode] Sort Colors
Sort Colors
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.
click to show follow up.
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 an one-pass algorithm using only constant space?
解题思路：
很容易想到用三个队列存储不同颜色的对象，然后将三个队列合并，相当于扫描了2次数组，时间复杂度为O(n)，空间复杂度为O(n)。但是这里要求只扫描一次，且空间复杂度为O(1)。三种值和两种值的排序问题可以用两边夹的办法，代码如下：
class Solution {
public:
void sortColors(int A[], int n) {
int i = 0, redStart = 0, blueStart = n - 1;
while(i < blueStart + 1){
if(A[i] == 0){
swap(A, redStart, i);
redStart++;
i++;
}else if(A[i] == 2){
swap(A, blueStart, i);
blueStart--;
}else{
i++;
}
}
}
private:
void swap(int A[], int i, int j){
if(i == j){
return;
}
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
};二次刷题2015-10-10
class Solution {
public:
void sortColors(vector<int>& nums) {
int len = nums.size();
int flag0 = 0, flag1 = len, flag2 = len;
while(flag0<flag1){
if(nums[flag0]==0){
flag0++;
}else if(nums[flag0]==1){
swap(nums, flag0, flag1 - 1);
flag1--;
}else{
swap(nums, flag0, flag2 - 1);
flag2--;
flag1 = min(flag1, flag2);
}
}
}
void swap(vector<int>& nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
};
0 条评论