My 4ms C++ solution with Space O(1)


  • 0
    M

    class Solution {
    public:
    void sortColors(vector<int>& nums) {

        //one-pass (works like quick sort)
        
        vector<int>::iterator scanup, scandown;
        scanup = nums.begin();
        scandown = nums.end() - 1;
        
        for(int i=0; i < 2; i++)
        {
            scandown = nums.end() - 1;
            while(scanup < scandown )
            {
                while(*scanup == i && scanup < scandown)
                    ++ scanup;
                while(*scandown !=i && scandown > scanup)
                    -- scandown;
                    
                if(scanup > scandown)
                    break;
                int temp = *scanup;
                *scanup = *scandown;
                *scandown = temp;
            }
        }
        
    }
    

    };


  • 0
    C

    It's an unique solution, but its surely not O(1).


Log in to reply
 

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