【LeetCode】顔色分類（JavaScript）

題目：

給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顔色的元素相鄰，并按照紅色、白色、藍色順序排列。

此題中，我們使用整數 0、 1 和 2 分别表示紅色、白色和藍色。

注意:

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

示例:

輸入: [2,0,2,1,1,0]

輸出: [0,0,1,1,2,2]

方法一：暴力法

直接通過兩個 for 循環周遊數組，從 nums[0] 開始，選出一個最小的并且 <nums[i] 的數與其交換。

時間複雜度O（N^2）。

var sortColors = function(nums) {
    for(var i=0;i<nums.length;i++){
        var min = nums[i];
        var n = i;
        for(var j=i+1;j<nums.length;j++){
            if(min>nums[j]){
                min = nums[j];
                n = j;
            }
        }
        nums[n] = nums[i];
        nums[i] = min;
    }
};
           

方法二：直接修改法（感覺是最簡單的）

分别記錄有多少個紅色、白色、藍色，直接for循環修改。

時間複雜度O（N）。

var sortColors = function(nums) {
    let red = 0 , white = 0 , blue = 0;
    for(let i=0;i<nums.length;i++){
        if(nums[i] == 0)
            red++;
        else if(nums[i] == 1)
            white++;
        else
            blue++;
    }
    for(let i=0;i<red;i++){
        nums[i] = 0;
    }
    for(let i=red;i<red+white;i++){
        nums[i] = 1;
    }
    for(let i=red+white;i<red+white+blue;i++){
        nums[i] = 2;
    }
};
           

方法三：三指針法

因為隻有三個數字，1放在中間，0在左邊，2在右邊。是以比較如果 nums[cur]==0 ，就和 nums[p] 交換，并且兩個指針加一，如果 nums[cur]=2 ，就和 nums[p2] 交換，并且 p2–，否則移動 cur。這裡與左邊交換的時候cur++的原因是，nums[p] 的位置之前比較過，和左邊交換的時候，交換過來的數不可能是2（是2的話早就交換到右邊去了）。

時間複雜度O（N）。

var sortColors = function(nums) {
    let p=0,cur=0;
    let p2=nums.length-1;
    for(let i=0;i<nums.length;i++){
        if(nums[cur]==0){
            let temp = nums[cur];
            nums[cur++] = nums[p];
            nums[p++] = temp;
        }else if(nums[cur]==2){
            let temp = nums[cur];
            nums[cur] = nums[p2];
            nums[p2--] = temp;
        }else{
            cur++;
        }
    }
};
           

本文為作者關于LeetCode的解法

大神解法請自行搜尋