4ms c++ one pass with recursion, easy to understand


  • 0
    M

    The idea is simple, from the tail of the list, each time add one element and make sure this element and the array to the right sorts correctly

    class Solution {
    public:
        int colorSet[3] = {0, 0, 0};
    
        void swap(int* a, int* b)
        {
            int temp = *a;
            *a = *b;
            *b = temp;
        }
    
        void sortColors2(int head, vector<int>& nums)
        {
            int color = nums[head];
            if (head == nums.size() - 1)
            {
                colorSet[color]++;
                return;
            }
            else
            {
                sortColors2(head + 1, nums);
                if (color == 0)
                {
                    // Do nothing
                }
                else if (color == 1)
                {
                   // swap the head with the last '0'
                    swap(&nums[head], &nums[head + colorSet[0]]);
                }
                else if (color == 2)
                {
                    // swap the head with the last '0'
                    swap(&nums[head], &nums[head + colorSet[0]]);
                    // swap the '2 with the last '1'
                    swap(&nums[head + colorSet[0]], &nums[head + colorSet[0] + colorSet[1]]);
                }
                colorSet[color]++;
            }
        }
    
        void sortColors(vector<int>& nums) {
            sortColors2(0, nums);
        }
    };

Log in to reply
 

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