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.
Solution #2: (one-pass solution)
https://linchicoding.wordpress.com/2014/08/26/leetcode-sort-colors/
Solution #1: (two-pass counting sort as the follow up says)
http://group.jobbole.com/8144/
http://yucoding.blogspot.com/2013/05/leetcode-questions-99-sort-colors.html
Read full article from 一天一学: LeetCode - Sort Colors
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Solution #2: (one-pass solution)
https://linchicoding.wordpress.com/2014/08/26/leetcode-sort-colors/
public
void
sortColors(
int
[] A) {
if
(A.length==
0
)
return
;
int
red =
0
;
int
blue = A.length-
1
;
int
i =
0
;
while
(i <= blue){
if
(A[i]==
0
){
//swap with red
A[i] = A[red];
A[red] =
0
;
red++;
}
if
(A[i]==
2
){
//swap with blue
A[i] = A[blue];
A[blue] =
2
;
blue--;
i--;
//---!!!--important--for case A[i]=0 then swaped to 2, it go through both branches
//--but for case A[i] = 2 then switch to 0, need to decrease i so can enter first branch
}
i++;
}
}
public
void
sortColors(
int
[] A) {
if
(A ==
null
|| A.length ==
0
|| A.length ==
1
)
return
;
// one-pass solution
int
red =
0
, blue = A.length -
1
, tmp, i =
0
;
// stop looping when current >= blue
while
(i <= blue) {
// if color is red, move to the front
if
(A[i] ==
0
) {
// when cur > red, switch
if
(i > red) {
tmp = A[red];
A[red] = A[i];
A[i] = tmp;
red++;
}
// when cur <= red, no need to switch, just move both to next
else
{
i++;
red++;
}
}
// if color is blue, move to the end
else
if
(A[i] ==
2
) {
// when cur < blue, switch
if
(i < blue) {
tmp = A[blue];
A[blue] = A[i];
A[i] = tmp;
blue--;
}
// when cur >= blue, end the loop
else
{
return
;
}
}
// if color is white, skip
else
{
i++;
}
}
}
public
void
sortColors(
int
[] A) {
if
(A ==
null
|| A.length ==
0
|| A.length ==
1
)
return
;
int
red =
0
, white =
0
, blue =
0
;
for
(
int
i =
0
; i < A.length; i++) {
if
(A[i] ==
0
) red++;
else
if
(A[i] ==
1
) white++;
else
blue++;
}
for
(
int
i =
0
; i < red; i++)
A[i] =
0
;
for
(
int
i = red; i < red + white; i++)
A[i] =
1
;
for
(
int
i = red + white; i < A.length; i++)
A[i] =
2
;
}
http://yucoding.blogspot.com/2013/05/leetcode-questions-99-sort-colors.html
Read full article from 一天一学: LeetCode - Sort Colors