4ms c++ code one pass O(1) in space


  • 2
    J
    void sortColors(vector<int>& nums) {
        if(nums.size()<2) return;
        int left = 0, right = (int)nums.size()-1;
        while(left<=right && nums[left]==0) left++;
        while(right>=left && nums[right]==2) right--;
        if(left>=right) return;
        int a = left;
        while (a<right) {
            if (nums[a]==0) {
                swap(nums[a], nums[left]);
                a++;left++;
            } else if(nums[a]==2) {
                swap(nums[a], nums[right]);
                right--;
                while(nums[right]==2) right--;
                if(nums[a]==1) a++;
            } else a++;
        }
        if(nums[a]==0) swap(nums[a], nums[left]);
    }

Log in to reply
 

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