My Template for this kind of problem

• One can use this template to handle this kind of "sorting" problems. No matter how many colors from 0 to n, or different labels as "red", "blue", etc.

We can simply put them in the cand array, then do the sorting.

``````public class Solution {
public void sortColors(int[] nums) {
int[] cand = {0, 1, 2};
int start=0;
for(int i=0;i<3;i++){
while(start<nums.length && nums[start]==cand[i]) start++;
for(int j=start;j<nums.length;j++){
if(nums[j]==cand[i]){
swap(nums, j, start++);
}
}
}
return;
}
public void swap(int[] nums, int a, int b){
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
}
``````

• This post is deleted!

• Kudos for the template.
Slight optimization.

``````public class Solution {
public void sortColors(int[] nums) {
if (nums.length < 2) return;
int [] cand = {0,1,2};
int start = 0;
for (int i = 0 ; i < cand.length; i++) {
while (start < nums.length && nums[start] == cand[i]) start ++;
if (start >= nums.length) return;
for (int j = start+1; j < nums.length; j++) {
if (nums[j] == cand[i]) {
swap (nums,j,start);
start++;
}
}
}
}
private void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
``````

• I have a probably clearer and cleaner template for it

``````void partition(vector<int> & nums, vector<int> const & pivots)
{
vector<int> boundaries(pivots.size());
for (auto &n : nums)
{
for (int i = 0; i < pivots.size(); ++ i)
if (n < pivots[i])
swap(n, nums[boundaries[i] ++]);
for (int i = 1; i < pivots.size(); ++ i)
boundaries[i] = max(boundaries[i], boundaries[i - 1]);
}
}
``````

test:

``````int main()
{
vector<int> input = {0,12,43,3,123,12,3,13,43,5,35,37,6,5,8,9,68,26,34,6,8,65,7,6,4,56,4,5};
vector<int> pivots = {10,20,30,40,50,100};
partition(input, pivots);
for (auto n : input)
cout<<n<<",";
///0,3,3,5,6,5,8,9,6,8,7,6,4,4,5,12,12,13,26,35,34,37,43,43,56,65,68,123,
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.