题目

题解

代码

public class code75 {

    // public static void sortColors(int[] nums) {
    // int count_0 = 0;
    // int count_1 = 0;
    // int count_2 = 0;
    // for (int i = 0; i < nums.length; i++) {
    // if (nums[i] == 0) {
    // count_0++;
    // } else if (nums[i] == 1) {
    // count_1++;
    // } else if (nums[i] == 2) {
    // count_2++;
    // }
    // }

    // int i;
    // for (i = 0; i < count_0; i++) {
    // nums[i] = 0;
    // }
    // for (; i < count_0 + count_1; i++) {
    // nums[i] = 1;
    // }
    // for (; i < count_0 + count_1 + count_2; i++) {
    // nums[i] = 2;
    // }
    // }

    public static void sortColors(int[] nums) {
        // 对于所有 idx < i : nums[idx < i] = 0
        // idx 是当前考虑元素的下标
        int p0 = 0;
        int cur = 0;
        // 对于所有 idx > k : nums[idx > k] = 2
        // idx 是当前考虑元素的下标
        int p2 = nums.length - 1;

        while (cur <= p2) {
            if (nums[cur] == 0) {
                swap(nums, cur, p0); // 交换第 p0 个和第 cur 个元素
                cur++;
                p0++;
            } else if (nums[cur] == 2) {
                swap(nums, cur, p2); // 交换第 p2 个和第 cur 个元素
                p2--;
            } else if (nums[cur] == 1) {
                cur++;
            }
        }
    }

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

    public static void main(String[] args) {
        int nums[] = { 2, 0, 2, 1, 1, 0 };
        sortColors(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
    }
}
75. 颜色分类

题目

题解

代码

参考
