【双指针】75. 颜色分类、荷兰国旗问题

75. 颜色分类

给定一个包含红色、白色和蓝色、共 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

进阶：

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

单指针两次遍历

class Solution {
    public void sortColors(int[] nums) {
        var len = nums.length;
        var count = 0;
        for(var i = 0; i < len; i++) {
            if(nums[i] == 0) {
                var temp = nums[i];
                nums[i] = nums[count];
                nums[count++] = temp;
            }
        }

        for(var i = count; i < len; i++) {
            if(nums[i] == 1) {
                var temp = nums[i];
                nums[i] = nums[count];
                nums[count++] = temp;
            }
        }
    }
}

双指针一次遍历

• 使用两个指针i、j，分别指向数组开头连续的0、连续的1的最后一位
• 使用k遍历数组，
  • 如果值为1，则存储到j的位置（交换nums[j]和nums[k]），然后j++
  • 如果值为0，存储到i（交换nums[i]和nums[k]），但是此时i的位置可能已经存储了1，所以：
    • 如果i < j，说明i的位置确实存储了1，所以上面交换完后nums[k]为1，再将其和nums[j++]交换，这样原本最前面的1就到了连续的1的最后面了
    • i++、j++，因为前移了一个0，所以i、j指针都需要后移

class Solution {
    public void sortColors(int[] nums) {
        var n = nums.length;

        var i = 0;
        var j = 0;

        for(var k = 0; k < n; k++) {
            if(nums[k] == 0) {
                var temp = nums[k];
                nums[k] = nums[i];
                nums[i] = temp; 
                if(i < j) {
                    temp = nums[k];
                    nums[k] = nums[j];
                    nums[j] = temp;
                }
                i++;
                j++;
            } else if(nums[k] == 1) {
                var temp = nums[k];
                nums[k] = nums[j];
                nums[j++] = temp; 
            }
            // System.out.println(Arrays.toString(nums));
        }
    }
}