给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？
*/ C++ 解法 class Solution { public: void sortColors(vector<int>& nums) { vector<int> colors(3); for (int num : nums) ++colors[num]; for (int i = 0, cur = 0; i < 3; i++) { for (int j = 0; j < colors[i]; j++){ nums[cur++] = i; } } } }; */ class Solution { public: void sortColors(vector<int>& nums){ int red = 0, blue = nums.size()-1; for(int i = 0; i <= blue; i++){ if (nums[i] == 0){ swap(nums[i], nums[red++]); } else if (nums[i] == 2){ swap(nums[i--], nums[blue--]); } } } }; */ class Solution { public: void sortColors(vector<int>& nums){ int left = 0, right = nums.size()-1, cur = 0; while(cur<=right){ if (nums[cur] == 0) { swap(nums[cur++], nums[left++]); }else if (nums[cur] == 2) { swap(nums[cur], nums[right--]); }else { cur++; } } } }; */Python 解法 class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ c0, c1 ,c2 =0,0,0 for i in nums: if i == 0: c0 +=1 if i == 1: c1 +=1 if i == 2: c2 += 1 nums[:c0] = [0]*c0 nums[c0:c0+c1] = [1]*c1 nums[c0+c1:] = [2]*c2 */ class Solution: def sortColors(sef,nums): left = 0 right = len(nums)-1 i = 0 while i<= right: if nums[i] == 2: nums[i], nums[right] = nums[right], nums[i] right -=1 elif nums[i] == 0: nums[i], nums[left] = nums[left], nums[i] left +=1 i +=1 else: i+=1