李成笔记网

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

package leetcode;

public class SortColors_75 {
    public void SortColors(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        // 0 and 2
        while (i < j) {
            if (nums[i] <= 1) {
                i++;
                continue;
            }
            if (nums[j] >= 1) {
                j--;
                continue;
            }
            // 交换i j
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }

        // 0 and 1
        i = 0;
        j = nums.length - 1;
        while (i < j) {
            if (nums[i] == 0) {
                i++;
                continue;
            }
            if (nums[j] >= 1) {
                j--;
                continue;
            }
            // 交换i j
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }

        // 1 and 2
        i = 0;
        j = nums.length - 1;
        while (i < j) {
            if (nums[i] <= 1) {
                i++;
                continue;
            }
            if (nums[j] > 1) {
                j--;
                continue;
            }
            // 交换i j
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
        // 如果相等。 判断是0 向左， 1 结束 2 向右
//        if (nums[i] > 1) {
//            for (int k = i + 1; k < nums.length - 1; k++) {
//                if (nums)
//            }
//        }
//        if (nums[j] < 1) {
//
//        }
    }

    public static void main(String[] args) {
        SortColors_75 sortColors_75 = new SortColors_75();
       // int[] nums = {2, 0, 2, 1, 0, 2, 1, 1, 0};

        int[] nums = {1, 0, 1};
        // 0 0 2 1 0 2 1 1 2
        // 0 0 0 1 2 2 1 1 2
        //
        sortColors_75.SortColors(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.printf(" " + nums[i]);
        }
    }
}