【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的解法

大神解法请自行搜索