颜色分类 | 徐年の博客

力扣 75. 颜色分类

题目说明

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

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

提示：
- n == nums.length
- 1 <= n <= 300
- nums[i] 为 0、1 或 2

示例

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现我们可以将 2 和 0 放在该在的位置，1 的位置自然也就确定了，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 数组
     * 双指针
     */
    public void sortColors(int[] nums) {
        int n = nums.length;
        // 标记 0 和 2 的位置
        int tick0 = 0, tick2 = n - 1;

        // 将2和0放置到合适的位置后,1就在自己的位置了
        for (int i = 0; i <= tick2; ++i) {
            // 如果当前值等于2,就不断向数组尾部置换
            while (i <= tick2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[tick2];
                nums[tick2] = temp;
                --tick2;
            }
            // 置换完之后,如果当前位置是 0, 则可以将它与 0 标志数交换
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[tick0];
                nums[tick0] = temp;
                ++tick0;
            }
        }

    }
}