Share my C++ short one-pass solution(constant memory), easy to understand


  • 0
    E

    I use 3 pointers to indicate the position of 0, 1 and 2. i points to 0, j points to 1, k points to 2. Initially, i is 0 , k is n-1, and j walk between i and k.

    If nums[j] is 0, then swap nums[i] and nums[j]. If nums[j] is 1, pass. If nums[j] is 2, then swap nums[j] and nums[k].

    Here is my code,

    class Solution {
    public:
        void sortColors(vector<int>& nums) {
            if(nums.empty()) return;
            int n = nums.size();
            int i=0,j=0,k=n-1;
            
            while(j <= k){
                if(nums[j]==0) {
                    int tmp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = tmp;
                    i++;
                    j++;
                }
                else if (nums[j]==1) j++;
                else if (nums[j]==2) {
                    int tmp = nums[j];
                    nums[j] = nums[k];
                    nums[k] = tmp;
                    k--;
                }
                
            }
        }
    };
    

Log in to reply
 

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