首页 > 代码库 > Sort Colors

Sort Colors

2024-07-05 15:34:01   223人阅读

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.

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?

由于只有0,1,2这三个值，提示中又说用常数空间一次遍历，就想到了类似快排的做法，想法就是将所有的0移动到1左边，2移动到1右边，因为1的个数不止一个，所以要添加一个变量。具体思路如下：

类似快排的做法，初始化start=0,end=length-1,pos=0;pos表示第一个1所在的位置，表示该位置之前的都是0

1，从后向前，end--，直到找到第一个小于等于1的，与pos交换，若找到的为0，则pos++;

2，从前向后，start++，直到找到第一个等于2的，在start++的过程中，若pos <= start && A[start] == 0，交换start和pos并且pos++，找到第一个等于2的后，交换start和end

3，重复上述步骤，直到start>end。

代码如下：

 1 int start = 0;
 2         int pos = 0;
 3         int end = A.length - 1;
 4         while (pos <= start && start <= end) {
 5             while (start <= end && A[end] == 2) {
 6                 end--;
 7             }
 8             if (pos <= start && start <= end) {
 9                 swap(A, pos, end);
10                 if (A[pos] == 0) {
11                     pos++;
12                 }
13             }
14             while (start <= end && A[start] <= 1) {
15                 if (pos <= start && A[start] == 0) {
16                     swap(A, start, pos);
17                     pos++;
18                 }
19                 start++;
20             }
21             if (pos <= start && start <= end) {
22                 swap(A, start, end);
23             }
24         }


联系
我们