讨论/《数组类算法》 - 颜色分类/
《数组类算法》 - 颜色分类
共 30 个回复

分而治之

class Solution {
    public void sortColors(int[] nums) {
        int zeroNum = 0;
        int oneNum = 0;
        int twoNum = 0;

        for (int i : nums) {
            switch (i) {
                case 0:
                    ++zeroNum;
                    break;
                case 1:
                    ++oneNum;
                    break;
                case 2:
                    ++twoNum;
                    break;
                default:
            }
        }

        for (int i = 0; i < zeroNum; i++) {
            nums[i] = 0;
        }

        for (int i = 0; i < oneNum; i++) {
            nums[zeroNum + i] = 1;
        }

        for (int i = 0; i < twoNum; i++) {
            nums[zeroNum + oneNum + i] = 2;
        }
    }
}
13

Java 0ms 100.0%

class Solution {
    public void sortColors(int[] nums) {
        int redIndex = 0;
        int blueIndex = nums.length - 1;

        // 把红色和蓝色放在两边,中间自然就是白色
        for (int i = 0; i < blueIndex + 1; i++){
            if (nums[i] == 0){
                int tmp = nums[redIndex];
                nums[redIndex++] = nums[i];
                nums[i] = tmp;
            }else if (nums[i] == 2){
                int tmp = nums[blueIndex];
                nums[blueIndex--] = nums[i];
                nums[i] = tmp;
                // 避免遗漏
                i--;
            }
        }
    }
}
3

这不是三色旗子那个快排的用法么

void temp(int* nums, int a,int b);
void sortColors(int* nums, int numsSize){
    int low , mid , high;
    low = mid = 0;
    high = numsSize-1;
    while(mid<=high){
        if(nums[mid]==0){
            temp(nums,low,mid);
            low++;
        }
        if(nums[mid]==2){
            temp(nums,mid,high);
            high--;
        }else{
            mid++;
        }
    }
    
}
void temp(int* nums,int a,int b){
    int t;
    t = nums[a];
    nums[a] = nums[b];
    nums[b] = t;
}
3

多么丑陋的代码

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let totalRed = 0;
    let totalBlue = nums.length - 1;
    nums.forEach((item, index)=>{
        if (index <= totalBlue) {
            switch(item) {
                case 0: {
                    move0(index);
                    break;
                }
                case 1: break;
                case 2: {
                    move2(index);
                }
            }
        }
    });
    function move2(index) {
        // 获取末尾 非2数
        while (nums[totalBlue] === 2) totalBlue--;
        if (index > totalBlue) return;
        // 如果前方有位置, 前置
        if (index !== totalBlue) {
            [nums[index], nums[totalBlue]] = [nums[totalBlue], nums[index]];
            totalBlue--;
            // 处理换回来的1
            if (nums[index] === 0) {
                move0(index);
            }
        }
    }
    function move0(index) {
        // 前置0, 补齐1
        if (totalRed !== index) nums[index] = 1;
        nums[totalRed++] = 0;
    }
};

3

使用左右快慢指针方法,从左至右遍历一遍数组,如果为0则根据左边的慢指针存储,左边慢指针往右移动,快指针i加1,如果为2则根据右边慢指针存储,然后右边慢指针往左移动,需要注意的是右边慢指针移动后快指针i不能加1了,因为左右交换后还得对快指针i的数进行判断,如果为1则不管,直接i++就可以了,终止条件为快指针i<=右边慢指针就可以了。
代码如下:

class Solution {
    public void sortColors(int[] nums) {
        int n=nums.length;
        int left=0;
        int ens=n-1;
        int i=0;
        while(i<=ens)
        {
            if(nums[i]==0)
            {
                int temp=nums[left];
                nums[left]=nums[i];
                nums[i]=temp;
                left++;
                i++;
            }
            else if(nums[i]==2)
            {
                int temp=nums[ens];
                nums[ens]=nums[i];
                nums[i]=temp;
                ens--;
            }
            else
            {
                i++;
            }

        }

    }
}
1
class Solution {
    public void sortColors(int[] nums) {
        int i = 0, j = nums.length - 1;
        for(int k = 0; k <= j; k++) {
            if(nums[k] == 0) {
                swap(nums, i++, k);
            } else if(nums[k] == 2) {
                swap(nums, j--, k--);
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

注意与j交换时k不能动,避免漏掉部分情况

1

Python3

"""
思路: 将红色0放在最左边; 将蓝色2放在最右边;剩下的就是白色1
方法: 双指针+遍历数组
"""
n = len(nums)-1
i = 0
l = 0
r = n
while(i <= r):
    if nums[i] == 0:
        nums[l],nums[i] = nums[i],nums[l]
        l += 1
        i += 1
    elif nums[i] == 2:
        nums[r],nums[i] = nums[i],nums[r]
        r -= 1
    else:
        i += 1
1

思路:遇到0则和前面的0指针zeroPos所指向的位置交换,遇到2则和2指针twoPos所指向位置交换,如果发现交换到当前位置i的元素还是0或者2,那就让i回退一位,在下一轮循环中再重新从这个位置检查交换。

 void sortColors(vector<int>& nums) {
        if(nums.size()<=0)
            return;
        //都代表了当前需要插入的位置
        int zeroPos=0;
        int twoPos=nums.size()-1;
        for(int i = 0;i<=twoPos;i++){
          if (nums[i] == 0)
                swap(nums[zeroPos++], nums[i]);
          if (nums[i] == 2)
                swap(nums[twoPos--], nums[i]);
          if (nums[i] != 1)
                i = max(zeroPos, i) - 1;//用max是为了保证i总在0指针的后面
        }
    }
1
class Solution {
public:
    void sortColors(vector<int>& nums) {

        int l=-1;
        int r=nums.size();
        int i=0;
        while(i<r){

            if(nums[i]==0){

                ++l;
                swap(nums[i],nums[l]);
                ++i;
            }
            else if(nums[i]==2){

                --r;
                swap(nums[i],nums[r]);//交换完这一步i是不能+1的,因为可能换的是0,如果+1就把这个0忽略了
            }
            else
                ++i;
        }
    }
};
1

感觉这种好理解吧 时间复杂度 O(n) 还能接受的吧