[Lintcode] Sort Color II | XiaoHuaHua's Blog
Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
http://www.cnblogs.com/EdwardLiu/p/4395457.html
Read full article from [Lintcode] Sort Color II | XiaoHuaHua's Blog
Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.
Similar to [Lintcode] Sort Colors, we use partition subroutine for k-1 times.
void sortColors2(vector<int> &colors, int k) {
// write your code here
auto r = colors.size()-1;
for(auto i=0;i<k-1;++i)
r = partition(colors, 0, r, k-i-1);
}
private:
int partition(vector<int> &nums, int l, int r, int pivot)
{
int i=l, j=r;
while(i<=j)
{
while(i<r && nums[i] <= pivot) ++i;
while(j>0 && nums[j] > pivot) --j;
if(i<=j) swap(nums[i++], nums[j--]);
}
return i-1;
}
http://www.cnblogs.com/yuzhangcmu/p/4177326.htmlpublic void sortKColors(int[] colors, int k) { 3 // write your code here 4 if (colors == null) { 5 return; 6 } 7 8 int len = colors.length; 9 for (int i = 0; i < len; i++) { 10 // Means need to deal with A[i] 11 while (colors[i] > 0) { 12 int num = colors[i]; 13 if (colors[num - 1] > 0) { 14 // 1. There is a number in the bucket, 15 // Store the number in the bucket in position i; 16 colors[i] = colors[num - 1]; 17 colors[num - 1] = -1; 18 } else if (colors[num - 1] <= 0) { 19 // 2. Bucket is using or the bucket is empty. 20 colors[num - 1]--; 21 // delete the A[i]; 22 colors[i] = 0; 23 } 24 } 25 } 26 27 int index = len - 1; 28 for (int i = k - 1; i >= 0; i--) { 29 int cnt = -colors[i]; 30 31 // Empty number. 32 if (cnt == 0) { 33 continue; 34 } 35 36 while (cnt > 0) { 37 colors[index--] = i + 1; 38 cnt--; 39 } 40 }http://blog.xiaohuahua.org/2015/01/24/lintcode-sort-colors/
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Solution #2. Since there are only 3 different values in the array, we can use partition subroutine twice. first pass on pivot 1, second pass on pivot 0
void sortColors(vector<int> &nums) {
// write your code here
int l = 0, r = nums.size()-1;
int m = partition(nums, 0, r, 1);
partition(nums, 0, m, 0);
}
int partition(vector<int> &nums, int l, int r, int pivot)
{
int i=l, j=r;
while(i<=j)
{
while(i<r && nums[i] <= pivot) ++i;
while(j>0 && nums[j] > pivot) --j;
if(i<=j) swap(nums[i++], nums[j--]);
}
return i-1;
}http://www.cnblogs.com/EdwardLiu/p/4395457.html
Read full article from [Lintcode] Sort Color II | XiaoHuaHua's Blog
