题目描述
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
方法1:
用这道题默写了下三向切分的快排
class Solution { public: void quicksort(vector<int>& nums,int left,int right){ if(left>=right) return; srand(time(0)); int pivot = rand() % (right - left + 1) + left; swap(nums[left],nums[pivot]); int v=nums[left]; int lt=left,gt=right,i=left+1; while(i<=gt){ if(nums[i]<v) swap(nums[i++],nums[lt++]); else if(nums[i]>v) swap(nums[i],nums[gt--]); else i++; } quicksort(nums,left,lt-1); quicksort(nums,gt+1,right); } void sortColors(vector<int>& nums) { quicksort(nums,0,nums.size()-1); } };
方法2:
当然,最简单的还是直接sort
class Solution { public: void sortColors(vector<int>& nums) { sort(nums.begin(),nums.end()); } };
方法3:
用单指针,先找到0,全通过交换放最前面,再找1,通过交换放在0后面,以此类推
为了提高通用性,把0,1,2,放数组了
class Solution { public: void sortColors(vector<int>& nums) { int flag[3]={0,1,2}; int ptr=0; for(auto color:flag){ for(int i=0;i<nums.size();i++){ if(nums[i]==color) swap(nums[i],nums[ptr++]);//ptr前都是排过顺序的 } } } };