重温算法之颜色分类

作者：自由

2022 年 7 月 12 日
本文字数：662 字
阅读完需：约 2 分钟

一.题目介绍

1.题目来源

2.题目

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

二.具体实现

1.实现思路

通过提示我们可以容易想到头尾各用一个指针，然后一次遍历，遇到红色就与头部置换，遇到蓝色就与尾部置换，其中遇到蓝色时，需要判断尾部之前为红色的场景，此时通过将 index 减一，可以避免代码添加额外判断。

2.实现代码

1)自己的实现方式

public void sortColors(int[] nums) {    int redIndex = 0;    int blueIndex = nums.length - 1;    for (int index = 0; index <= blueIndex; index++) {        if (nums[index] == 0) {            swap(nums, redIndex, index);            redIndex++;        }        if (nums[index] == 2) {            swap(nums, blueIndex, index);            blueIndex--;            index--;         }    }}
private void swap(int[] nums, int x, int y) {    int temp = nums[x];    nums[x] = nums[y];    nums[y] = temp;}复制代码