leetcode-75.Sort Colors
题面
给定数组,将红-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 };