One pass solution using constant space


  • 0
    P

    Range Represention: [start,end)

     void sortColors(vector<int>& nums) {
                //n0: end of 0
                //n1: start of unsorted
                //n2: start of 2
                int n0=0, n1=0, n2=nums.size();
                while(n1<n2)
                {
                    switch(nums[n1])
                    {
                        case 0:
                        {
                            if(n1!=n0)
                            {
                                swap(nums[n0], nums[n1]);
                            }
                            n0++;
                            n1++;
                            break;
                        }
                        case 1:
                        {
                            n1++;
                            break;
                        }
                        case 2:
                        {
                            n2--;
                            swap(nums[n1],nums[n2]);
                            break;
                        }
                    }
                    
                }
                
            }

Log in to reply
 

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