No.75 Sort Colors

No.75 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.

解法：

　　颜色排序：数组nums中包括代表红白蓝三色的0/1/2的n个数，
　　输出：经排序后，nums是有序的红白蓝即0/1/2有序排列
　　注意：0、1、2连续，可为数组下标，更简洁

 1 class Solution
 2 {
 3 public:
 4     void sortColors(vector<int> &nums)
 5     {//颜色排序：数组nums中包括代表红白蓝三色的0/1/2的n个数，
 6      //输出：经排序后，nums是有序的红白蓝即0/1/2有序排列
 7      //注意：0、1、2连续，可为数组下标，更简洁
 8         int count = nums.size();
 9         if(count <=1)
10             return;
11         int color[3] = {0};//颜色统计数组
12         
13         for(int i=0; i<count; i++)
14             color[nums[i]]++;//技巧
15 
16         for(int i=0,index=0; i<3; i++)
17             for(int j=0; j<color[i]; j++)
18                 nums[index++] = i;
19         //so简洁，so easy
20     }
21 };

我的笨代码：

 1 #include "stdafx.h"
 2 #include <vector>
 3 #include <iostream>
 4 using namespace std;
 5 
 6 class Solution
 7 {
 8 public:
 9     void sortColors(vector<int> &nums)
10     {//颜色排序：数组nums中包括代表红白蓝三色的0/1/2的n个数，
11      //输出：经排序后，nums是有序的红白蓝即0/1/2有序排列
12         int count = nums.size();
13         if(count <= 1)
14             return;
15 
16         //类似计数排序
17         int countRed = 0;
18         int countWhite = 0;
19         int countBlue = 0;
20         //从前向后遍历
21         for(int i=0; i<count; i++)
22         {
23             if(nums[i] == 0)
24                 countRed++;
25             else if(nums[i] == 1)
26                 countWhite++;
27             else if(nums[i] == 2)
28                 countBlue++;
29         }
30 
31         //根据统计结果，从前向后改变数组
32         for(int i=0; i<count; i++)
33         {
34             if(countRed != 0)
35             {
36                 nums[i] = 0;
37                 countRed--;
38                 continue;
39             }
40             if(countWhite != 0)
41             {
42                 nums[i] = 1;
43                 countWhite--;
44                 continue;
45             }
46             if(countBlue != 0)
47             {
48                 nums[i] = 2;
49                 countBlue--;
50                 continue;
51             }
52         }
53     }     
54 };
55 int main()
56 {
57     Solution sol;
58     int data[] = {0,2,1,2,1,2,0,0,0,1};
59     vector<int> test(data,data+sizeof(data)/sizeof(int));
60 
61     for(auto &i : test)
62         cout << i << " ";
63     cout << endl;
64     sol.sortColors(test);
65         for(auto &i : test)
66         cout << i << " ";
67     cout << endl;
68 
69     return 0;
70 }

View Code