Sort Colors — LeetCode「建议收藏」

public void sortColors(int[] A) {
    if(A==null || A.length==0)
        return;
    int[] res = new int[A.length];
    int[] helper = new int[3];
    for(int i=0;i<A.length;i++)
    {
        helper[A[i]]++;
    }
    for(int i=1;i<3;i++)
    {
        helper[i]=helper[i]+helper[i-1];
    }
    for(int i=A.length-1;i>=0;i--)
    {
        res[helper[A[i]]-1] = A[i];
        helper[A[i]]--;
    }
    for(int i=0;i<A.length;i++)
    {
        A[i] = res[i];
    }
}

上面的代码是计数排序的标准解法。能够看到总共进行了三次扫描，事实上最后一次仅仅是把结果数组拷贝到原数组而已。假设不须要in-place的结果仅仅须要两次扫描。


事实上就算返回元素组也能够是两次扫描，这须要用到元素仅仅有0,1,2的本质。我们知道helper[i]中是包括着0,1,2的元素数量，我们仅仅须要依照helper[0,1,2]的数量依次赋值过来就可以（每层循环把helper[i]–，假设helper[i]到0就i++就能够了）。仅仅是这样就不是计数排序比較标准的解法，我希望还是复习一下。


这样的方法的时间复杂度是O(2*n)，空间是O(k)，k是颜色的数量，这里是3。

上述方法须要两次扫描。我们考虑怎么用一次扫描来解决。事实上还是利用了颜色是三种这一点，道理事实上也简单。就是搞两个指针。一个指在当前0的最后一个下标，还有一个是指在当前1的最后一个下标（2不须要指针由于剩下的都是2了）。进行一次扫描，假设遇到0就两个指针都前进一步并进行赋值，假设遇到1就后一个指针前进一步并赋值。代码例如以下： 

public void sortColors(int[] A) {
    if(A==null || A.length==0)
        return;
    int idx0 = 0;
    int idx1 = 0;
    for(int i=0;i<A.length;i++)
    {
        if(A[i]==0)
        {
            A[i] = 2;
            A[idx1++] = 1;
            A[idx0++] = 0;
        }
        else if(A[i]==1)
        {
            A[i] = 2;
            A[idx1++] = 1;
        }
    }
}

上述方法时间复杂度还是O(n)。仅仅是仅仅须要一次扫描，空间上是O(1)（假设颜色种类是已知的话）。

这道题我认为主要还是熟悉一下计数排序。计数排序是线性排序中比較重要的一种，关于排序要搞个专题专门的复习一下。非常多排序的基本思想都对解题有帮助哈。