75. Sort Colors

My intuition is to use count sort. The running time will be O(2n)

1:  class Solution {  
2:  public:  
3:    void sortColors(vector<int>& nums) {  
4:      vector<int> colors(3, 0);  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        colors[nums[i]]++;  
7:      }  
8:      int k = 0;  
9:      for (int i = 0; i < 3; i++) {  
10:        for (int j = 0; j < colors[i]; j++) {  
11:          nums[k++] = i;  
12:        }  
13:      }  
14:    }  
15:  };  

Top voted solution is as following. Do note while loops and their order.

1:  class Solution {  
2:  public:  
3:    void sortColors(vector<int>& nums) {  
4:      int blue = nums.size()-1, red = 0;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        while (nums[i] == 2 && i < blue) swap(nums[i], nums[blue--]);   
7:        while (nums[i] == 0 && i > red) swap(nums[i], nums[red++]);  
8:      }  
9:    }  
10:  };