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.
如果current 當下不等於 i (顏色)
就往後找 看有沒有 如果找不到就換 下一個顏色
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
void sortColors(vector<int>& nums) {
int current=0;
int size=nums.size();
for(int i=0;i<3;i++){
int color=current;
while(color<size && current<size){
if(nums[current]!=i){
color=current+1;
while(color<size && nums[color]!=i)color++;
if(color<size){
int temp=nums[color];
nums[color]=nums[current];
nums[current]=temp;
}else break;
}
current++;
}
}
}
};
|
-----------
The solution requires the use of tracking 3 positions, the Low, Mid and High.
We assume that the mid is the "Unknown" area that we must evaluate.
If we encounter a 0, we know that it will be on the low end of the
array, and if we encounter a 2, we know it will be on the high end of
the array.
To achieve this in one pass without preprocessing (counting), we
simply traverse the unknown will generating the low and high ends.
Take this example:
Assume our input is: 1 0 2 2 1 0 (short for simplicity).
Running the algorithm by hand would look something like:
1 0 2 2 1 0
^ ^
L H
M
Mid != 0 || 2
Mid++
1 0 2 2 1 0
^ ^ ^
L M H
Mid == 0
Swap Low and Mid
Mid++
Low++
0 1 2 2 1 0
^ ^ ^
L M H
Mid == 2
Swap High and Mid
High--
0 1 0 2 1 2
^ ^ ^
L M H
Mid == 0
Swap Low and Mid
Mid++
Low++
0 0 1 2 1 2
^ ^ ^
L M H
Mid == 2
Swap High and Mid
High--
0 0 1 1 2 2
^ ^
L M
H
Mid <= High is our exit case
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
void sortColors(vector<int>& nums)
{
int tmp = 0, low = 0, mid = 0, high = nums.size() - 1;
while(mid <= high)
{
if(nums[mid] == 0)
{
tmp = nums[low];
nums[low] = nums[mid];
nums[mid] = tmp;
low++;
mid++;
}
else if(nums[mid] == 1)
{
mid++;
}
else if(nums[mid] == 2)
{
tmp = nums[high];
nums[high] = nums[mid];
nums[mid] = tmp;
high--;
}
}
}
};
|
