题面

给定数组,将红-0、白-1、蓝-2,原地排序,要求相同颜色在一起。

样例

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

算法(初级/垃圾)

遍历数组,统计0、1、2个数,在重新写入数组中。

O(n)

源码

 1 class Solution {
 2 public:
 3     void sortColors(vector<int>& nums) {
 4         int len = nums.size();
 5         if(len <= 1)
 6             return ;
 7         int count[3] = {0};
 8         for(int n : nums)
 9             count[n]++;
10         
11         int i = 0;
12         while(count[0]--)
13             nums[i++] = 0;
14         while(count[1]--)
15             nums[i++] = 1;
16         while(count[2]--)
17             nums[i++] = 2;
18     }
19 };