当前位置：首页 > article >正文

力扣算法Hot100——75. 颜色分类

article 2025/3/20 22:38:00

在这里插入图片描述

解法1：当然可以冒泡排序，时间复杂度O( $n^2$ )

解法2：单指针

循环两次，第一次循环将所有的 0 交换到前面；
第二次循环将所有的 1 交换到 0 的后面

class Solution {
    public void sortColorsBySinglePointer(int[] nums) {
        int zeroCnt = 0, p = 0;
        for (int i = 0; i < nums.length ; i++) {
            if (nums[i] == 0) {
                p = nums[zeroCnt];
                nums[zeroCnt] = 0;             
                nums[i] = p;
                zeroCnt++;
            }
        }
        // 继续沿着zeroCnt的位置放 1
        for (int i = 0; i < nums.length ; i++) {
            if (nums[i] == 1) {
                p = nums[zeroCnt];
                nums[zeroCnt] = 1;
                nums[i] = p;
                zeroCnt++;
            }
        }
    }
}