My Template for this kind of problem


  • 6

    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;
        }
    }
    

  • 0
    L
    This post is deleted!

  • 0
    L

    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;
        }
    }
    

  • 0
    F

    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,
    }
    

Log in to reply
 

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