【Check 85】2024-05-29 - 75. 颜色分类

[larscheng]

75. 颜色分类

[larscheng]

思路

双指针 方法1:

• p0表示每次交换0要放的位置，p1表示每次交换1要放的位置，默认为0
• 要求按照0，1，2，所以在交换完0之后，如果p0小于p1，说明p0处的1已经被交换到nums[i]了，此时需要再放回p1处

方法2:

• p0表示每次交换0要放的位置,默认为0
• p2表示每次交换2要放的位置，默认为length-1
• 遇到0直接与p0交换，p0+1
• 遇到2直接与p2交换，p2-1，但此时被交换过来的元素有可能还是2，所以需要循环处理，直到被交换过来的元素不是2
• 被交换过来的如果是2，则继续交换
• 被交换过来的如果是0，则与p0交换
• 被交换过来的如果是1，则无需调整
• 所以2的处理逻辑要先于0，否则会漏处理

O(n)/O(1)

代码

class Solution {

    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 =0,p1=0;
        for (int i = 0; i < n; i++) {
            if (nums[i]==1){
                int temp = nums[i];
                nums[i]=nums[p1];
                nums[p1] = temp;
                ++p1;
            } else if (nums[i]==0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                //把nums[i]的0与p0交换后，如果p0小于p1，说明在此前已经有1放在了p0处
                //此时需要把nums[i]与p1交换，重新把这个1放到前面
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                ++p0;
                ++p1;
            }
        }
    }
}

class Solution {

    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 =0,p2=n-1;
        for (int i = 0; i <= p2; i++) {
            //被交换过来的元素有可能也是2
            while (i <= p2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                --p2;
            }
            if (nums[i]==0){
                int temp = nums[i];
                nums[i]=nums[p0];
                nums[p0] = temp;
                ++p0;
            }
        }

    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)