LeetCode 75. Sort Colors題目分析

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:You are not suppose to use the library's sort function for this problem.

click to show follow up.

Subscribe to see which companies asked this question.

題目

給定一個包含紅，白，藍且長度為 n 的數組，将數組元素進行分類使相同顔色的元素相鄰，并按照紅、白、藍的順序進行排序。

我們可以使用整數 0，1 和 2 分别代表紅，白，藍。

注意事項

不能使用代碼庫中的排序函數來解決這個問題。

排序需要在原數組中進行。

樣例

給你數組 [1, 0, 1, 2], 需要将該數組原地排序為 [0, 1, 1, 2]。

分析

方法一

一個相當直接的解決方案是使用計數排序掃描2遍的算法。

首先，疊代數組計算 0,1,2 出現的次數，然後依次用 0,1,2 出現的次數去覆寫數組。

代碼

void sortColors(int A[]) {
    int n = A.length;
    int num0 = 0, num1 = 0, num2 = 0;
    
    for(int i = 0; i < n; i++) {
        if (A[i] == 0) ++num0;
        else if (A[i] == 1) ++num1;
        else if (A[i] == 2) ++num2;
    }
    
    for(int i = 0; i < num0; ++i) A[i] = 0;
    for(int i = 0; i < num1; ++i) A[num0+i] = 1;
    for(int i = 0; i < num2; ++i) A[num0+num1+i] = 2;
}           

複制

方法二

思路是，如果找到一個0，後面元素不用移動，因為0總是在前面，如果找到一個1，那麼後面的1和2都要加一，如果找到2，那麼2右移。

代碼

// one pass in place solution
void sortColors(int A[]) {
    int n = A.length;
    int n0 = -1, n1 = -1, n2 = -1;
    for (int i = 0; i < n; ++i) {
        if (A[i] == 0) 
        {
            A[++n2] = 2; A[++n1] = 1; A[++n0] = 0;
        }
        else if (A[i] == 1) 
        {
            A[++n2] = 2; A[++n1] = 1;
        }
        else if (A[i] == 2) 
        {
            A[++n2] = 2;
        }
    }
}           

複制

方法三

兩根指針記錄0和2的邊界位置，就是0的最右邊，2的最左邊，1在中間不用判斷

public void sortColors(int[] a) {
        int n = a.length;
        int second=n-1, zero=0;
            for (int i=0; i<=second; i++) {
                while (a[i]==2 && i<second) swap(a,i, second--);
                while (a[i]==0 && i>zero) swap(a,i, zero++);
            }
    }           

複制