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

  • 0

    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 {
        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;
                else if (nums[j]==1) j++;
                else if (nums[j]==2) {
                    int tmp = nums[j];
                    nums[j] = nums[k];
                    nums[k] = tmp;

Log in to reply

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