首页 > 代码库 > Sort colors系列
Sort colors系列
75. Sort Colors
问题描述:
给一个包含n个数字的数组,其中有0,1,2;排序使得所有相同的数字相邻,且按照0,1,2的顺序。
思路:
(1)计数排序:
需要扫两遍数组,一遍统计个数,第二遍开始摆放数字。
代码如下:
1 void sortColors(vector<int>& nums) { 2 int i=0,j=0,k=0; 3 int n=nums.size(); 4 for(int p=0;p<n;p++) 5 { 6 if(nums[p]==0) 7 i++; 8 else if(nums[p]==1) 9 j++; 10 else 11 k++; 12 } 13 for(int p=0;p<n;p++) 14 { 15 if(p<i) 16 nums[p]=0; 17 else if(p>=i&& p<i+j) 18 nums[p]=1; 19 else 20 nums[p]=2; 21 } 22 }
(2)如果只能扫一遍,很容易想到的就是左边存放0和1,右边存放2.两边往中间靠。
设置两个index,left记录第一个1的位置,left左边为0,right记录第一个非2的位置,right右边为2.
然后使用i从头到尾扫一遍,直到与right相遇。
i遇到0就换到左边去,遇到2就换到右边去,遇到1就跳过。
需要注意的是:由于left记录第一个1的位置,因此A[left]与A[i]交换后,A[left]为0,A[i]为1,因此i++;
而right记录第一个非2的位置,可能为0或1,因此A[right]与A[i]交换后,A[right]为2,A[i]为0或1,i不能前进,要后续判断。
由此该数组分为4段:[0,left)-->0; [left,i)-->1; [i,right]-->乱序; (right,n-1]-->2
0 0 0 1 1 1 2 1 0 2 1 2 2 2
^ ^ ^
left i right
最直接的方法就是partition方法,代码如下:
1 void sortColors(int A[], int n) { 2 int left = 0; 3 int right = n-1; 4 int i = 0; 5 while(i <= right) 6 { 7 if(A[i] == 0) 8 { 9 swap(A[left], A[i]); 10 left ++; 11 i ++; 12 } 13 else if(A[i] == 1) 14 { 15 i ++; 16 } 17 else 18 { 19 swap(A[i], A[right]); 20 right --; 21 } 22 } 23 }
(3)最漂亮的一种做法:
【最直观:平移插入】
1 void sortColors(int A[], int n) { 2 int i = -1; 3 int j = -1; 4 int k = -1; 5 for(int p = 0; p < n; p ++) 6 { 7 //根据第i个数字,挪动0~i-1串。 8 if(A[p] == 0) 9 { 10 A[++k] = 2; //2往后挪 11 A[++j] = 1; //1往后挪 12 A[++i] = 0; //0往后挪 13 } 14 else if(A[p] == 1) 15 { 16 A[++k] = 2; 17 A[++j] = 1; 18 } 19 else 20 A[++k] = 2; 21 } 22 23 }
Sort colors系列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。