My AC O(n) time and constant space DP solution with std::swap()


  • 0

    This is my DP solution, my thought is swap the value when needed with an one-pass algorithm. With the for loop, A[zeros] is the first '1', A[zeros + ones] is the first '2'.

    class Solution {
    public:
        void sortColors(int A[], int n) {
            int zeros = 0, ones = 0;
            for (int i = 0; i != n; ++i)
                if (A[i] == 0)
                {
                    std::swap(A[i], A[zeros + ones]);
                    std::swap(A[zeros + ones], A[zeros]);
    				zeros++;
                }
                else if (A[i] == 1)
                {
                    std::swap(A[i], A[zeros + ones]);
    				ones++;
                }
        }
    };

Log in to reply
 

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