(C++) A simple solution for Sort Colors with time complexity O(n) and space complexity O(1)


  • 1
    A

    Since the int numbers in array A lie in {0,1,2}, an array ,B, of size 3 can be used to record the number of each int. Then according to the records in B, update the elements of A orderly.

    class Solution {
    public:
        void sortColors(int A[], int n) {
            int num[3]={0,0,0};
            int N;
            for(int i=0;i<n;i++)
            {
                N=A[i];
                num[N]++;
            }
            int j=0;
            for(int i=0;i<3;i++)
            {
                while(num[i]--)
                {
                    A[j++]=i;
                }
            }
        }
    };

Log in to reply
 

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