How to minimize the number of swap?


  • 0
    U

    I am using 3 way partition for the sort colors problem. Is there anything we can do to reduce the number of swap operation for the elements?


  • 0
    S

    I m not sure about the swap operation, i believe using two stacks is much easier and quicker.


  • 0
    S
    class Solution {
    public:
    void sortColors(vector<int>& nums) {
        vector<int> blue;
        vector<int> white;
        vector<int> result;
        for(auto i:nums){
            if(i==0)
            result.push_back(i);
            if(i==1)
            white.push_back(i);
            if(i==2)
            blue.push_back(i);
        }
        for(auto i:white){
            result.push_back(i);
        }
        for(auto i:blue){
            result.push_back(i);
        }
        nums=result;
    }
    

    };


Log in to reply
 

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