Bucket sort, 8 lines


  • 0
    W
    void sortColors(int A[], int n) 
    {
        vector<int> v(3);
        for(int i = 0; i < n; i++)
          v[A[i]] += 1;
        int pos = 0;
        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < v[i]; j++)
            {
                A[pos] = i;
                pos++;
            }
        }
    }
    

    O(n) time and O(1) space


  • 0
    S

    in fact this is the same as the follow up information, count sort and two pass


Log in to reply
 

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