My O(n) and constant space solution with C++


  • 1
    S
     class Solution {
        public:
            void sortColors(int A[], int n) {
                int j=0;
                for(int i=0; i<n; i++) {
                    if(0 == A[i]) {
                        int temp = A[i];
                        A[i] = A[j];
                        A[j] = temp;
                        j++;
                    }
                }
                for(int i=j; i<n; i++) {
                    if(1 == A[i]) {
                        int temp = A[i];
                        A[i] = A[j];
                        A[j] = temp;
                        j++;
                    }
                }
            }
        };

  • 0
    M
    1. The STL has swap function :)
    2. No need to save the temp value at A[i], you know that it is a 0 (in first case) and a 1 (in the second case)

Log in to reply
 

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