C++ 4ms 4lines Dutch Flag


  • 1
    B

    see wikipedia for algorithm explaination
    https://en.wikipedia.org/wiki/Dutch_national_flag_problem

    class Solution {
    public:
        void sortColors(vector<int>& nums) 
        {
            int left = 0, right = nums.size()-1, pos = 0;
            for(int pos = 0; pos <= right; pos++)
            {
                if(nums[pos]==0 && left<pos) swap(nums[left++], nums[pos--]);
                if(nums[pos]==2 && pos<right) swap(nums[right--], nums[pos--]);
            }
        }
    };

  • 0
    H

    Hi, nums[pos--] in first if sentence is time wasting. No need to check the number swapped from head since its checked already.


Log in to reply
 

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