颜色分类( LeetCode 75 )
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
二、题目解析
设置 3 个索引，left 指向数组的开始位置，right 指向数组的结束位置，index 指向数组的开始位置。
我们让 index 从头开始向后移动，在移动的过程中，它指向的元素会出现三种情况：
1、如果 index位置上的元素值为 0，则说明是红色，要放在最前面去，此时最前面的那个元素被 left 指着，所以让 index 指向的元素和 left 指向位置上的元素进行交换，交换完毕之后，说明 0 已经在它应该在的位置，即在整个数组的左区域，所以 left 可以向后移动，index 也向后移动
2、如果若 index 位置上的元素值为 1，则说明是白色，就应该放在中间，不用管它，继续移动 index
3、如果 index 位置上的元素值为 2，则说明是蓝色，要放在最后面，此时最后面的那个元素被 right 指着，所以让 index 指向的元素和 right 指向位置上的元素进行交换，交换完毕之后，说明 2 已经在它改在的位置，即在整个数组的右区域，right 向前移动，但由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种，到了 index 后，还需要继续观察一轮，所以 index先不移动
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com/567.html
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 颜色分类( LeetCode 75 ):https://leetcode-cn.com/problems/sort-colors/
class Solution {
public void sortColors(int[] nums) {
// left 指向数组的开始的位置，它指向的位置左侧都是 0
int left = 0;
// right 指向数组的结束的位置，它指向的位置右侧都是 2
int right = nums.length - 1;
// index 指向数组的开始位置
int index = 0;
// index 向后移动，当它越过 right 时跳出循环，不需要再判断了
// 因为此时说明 index 右侧的都已经是 2
while( index <= right ){
// 获取当前的元素值
int cur = nums[index];
// 如果 index 位置上的元素值为 0
if(cur == 0){
// 说明是红色，要放在最前面去
// 最前面的那个元素被 left 指着，所以让 index 指向的元素和 left 指向位置上的元素进行交换
swap(nums,left,index);
// index 可以向后移动
index++;
// left 可以向后移动，它的左侧区域都是 0
left++;
// 如果 index 位置上的元素值为 1
}else if(cur == 1){
// 说明是白色，就应该放在中间，不用管它，继续移动 index
index++;
// 如果 index 位置上的元素值为 2
}else if(cur == 2){
// 说明是蓝色，要放在最后面
// 所以让 index 指向的元素和 right 指向位置上的元素进行交换
swap(nums,right,index);
// 由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种
// 交换到了 index 后，还需要继续观察一轮，所以 index 先不移动
right--;
}
}
}
// 通过中间变量，交换两个元素的值
// nums[i] 的值变为了 nums[j] 的值
// nums[j] 的值变为了 nums[i] 的值
private void swap(int[] nums, int i ,int j){
// 使用临时变量 temp，保存 nums[i] 的值
int temp = nums[i];
// nums[i] 的值修改为 nums[j] 的值
nums[i] = nums[j];
// nums[i] 的值修改为 temp 的值
nums[j] = temp;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com/567.html
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 颜色分类( LeetCode 75 ):https://leetcode-cn.com/problems/sort-colors/
class Solution {
public:
void sortColors(vector<int>& nums) {
// left 指向数组的开始的位置，它指向的位置左侧都是 0
int left = 0;
// right 指向数组的结束的位置，它指向的位置右侧都是 2
int right = nums.size() - 1;
// index 指向数组的开始位置
int index = 0;
// index 向后移动，当它越过 right 时跳出循环，不需要再判断了
// 因为此时说明 index 右侧的都已经是 2
while( index <= right ){
// 获取当前的元素值
int cur = nums[index];
// 如果 index 位置上的元素值为 0
if(cur == 0){
// 说明是红色，要放在最前面去
// 最前面的那个元素被 left 指着，所以让 index 指向的元素和 left 指向位置上的元素进行交换
swap(nums,left,index);
// index 可以向后移动
index++;
// left 可以向后移动，它的左侧区域都是 0
left++;
// 如果 index 位置上的元素值为 1
}else if(cur == 1){
// 说明是白色，就应该放在中间，不用管它，继续移动 index
index++;
// 如果 index 位置上的元素值为 2
}else if(cur == 2){
// 说明是蓝色，要放在最后面
// 所以让 index 指向的元素和 right 指向位置上的元素进行交换
swap(nums,right,index);
// 由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种
// 交换到了 index 后，还需要继续观察一轮，所以 index 先不移动
right--;
}
}
}
// 通过中间变量，交换两个元素的值
// nums[i] 的值变为了 nums[j] 的值
// nums[j] 的值变为了 nums[i] 的值
void swap(vector<int>& nums,int i ,int j) {
// 使用临时变量 temp，保存 nums[i] 的值
int temp = nums[i];
// nums[i] 的值修改为 nums[j] 的值
nums[i] = nums[j];
// nums[i] 的值修改为 temp 的值
nums[j] = temp;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com/567.html
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 颜色分类( LeetCode 75 ):https://leetcode-cn.com/problems/sort-colors/
class Solution:
def sortColors(self, nums: List[int]) -> None:
# left 指向数组的开始的位置，它指向的位置左侧都是 0
left = 0
# right 指向数组的结束的位置，它指向的位置右侧都是 2
right = len(nums) - 1
# index 指向数组的开始位置
index = 0
# index 向后移动，当它越过 right 时跳出循环，不需要再判断了
# 因为此时说明 index 右侧的都已经是 2
while index <= right :
# 获取当前的元素值
cur = nums[index]
# 如果 index 位置上的元素值为 0
if cur == 0 :
# 说明是红色，要放在最前面去
# 最前面的那个元素被 left 指着，所以让 index 指向的元素和 left 指向位置上的元素进行交换
self.swap(nums,left,index)
# index 可以向后移动
index += 1
# left 可以向后移动，它的左侧区域都是 0
left += 1
# 如果 index 位置上的元素值为 1
elif cur == 1 :
# 说明是白色，就应该放在中间，不用管它，继续移动 index
index += 1
# 如果 index 位置上的元素值为 2
elif cur == 2 :
# 说明是蓝色，要放在最后面
# 所以让 index 指向的元素和 right 指向位置上的元素进行交换
self.swap(nums,right,index)
# 由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种
# 交换到了 index 后，还需要继续观察一轮，所以 index 先不移动
right -= 1
# 通过中间变量，交换两个元素的值
# nums[i] 的值变为了 nums[j] 的值
# nums[j] 的值变为了 nums[i] 的值
def swap(self,nums: List[int], i : int ,j : int):
# 使用临时变量 temp，保存 nums[i] 的值
temp = nums[i]
# nums[i] 的值修改为 nums[j] 的值
nums[i] = nums[j]
# nums[i] 的值修改为 temp 的值
nums[j] = temp
End
本系列会每天更新一道算法题，如果觉得内容对你有帮助的话麻烦点个赞，我们下一道题目再见。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-12-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
