Leetcode 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

进阶：

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

解题思路

这道题我们直接尝试满足进阶条件，只用常数空间，及一趟扫描算法，来完成。

这是一道经典的「荷兰国旗问题」，我比较习惯用双指针法来做。

具体步骤：

• 定义左右两个指针，left和right
  • left指针表示：在left指针左边的元素都为0
  • right指针表示：在right指针右边的元素都为2
  • 在left和right中间：未排序的元素
• 再来一个指针 i，从left到right遍历
  • 如果元素为1，则什么都不做，i++
  • 如果元素为0，则与当前left指针所指位置元素做交换，left++，i++（可以i++，是因为left指针所指的元素，已经经过校验了，肯定不是2，所以可以直接跳过）
  • 如果元素为2，则与当前right指针所指位置元素做交换，right--（不要i++，因为此时移动到 i 位置的元素，还没有经过校验，有可能为0）

Java代码

class Solution {
    public void sortColors(int[] nums) {
        int l = 0, r = nums.length - 1, i = l;
        // 一定要带等号，否则这个位置会错过校验
        while(i <= r){
            if(nums[i] == 0){
                int tmp = nums[l];
                nums[l] = nums[i];
                nums[i] = tmp;
                // 注意：这里可以i++，因为left的元素肯定不是2
                l++;
                i++;
            }else if(nums[i] == 2){
                int tmp = nums[r];
                nums[r] = nums[i];
                nums[i] = tmp;
                // 注意：在这里不要进行i++，因为此时的i位置还不一定满足条件
                r--;
            }else{
                i++;
            }
        }
    }
}

总结

这道题的核心思路是双指针法，用两个指针，分别标记左边为0和右边为2的位置。再用一个指针遍历所有的元素，将元素交换到合适的位置。