颜色分类( LeetCode 75 )
本文内容为算法训练营一期内容,仅限训练营学员观看。
一、题目描述
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
二、题目解析
设置 3 个索引,left
指向数组的开始位置,right
指向数组的结束位置,index
指向数组的开始位置。
我们让 index
从头开始向后移动,在移动的过程中,它指向的元素会出现三种情况:
- 如果
index
位置上的元素值为 0,则说明是红色,要放在最前面去,此时最前面的那个元素被left
指着,所以让index
指向的元素和left
指向位置上的元素进行交换,交换完毕之后,说明 0 已经在它应该在的位置,即在整个数组的左区域,所以left
可以向后移动,index
也向后移动 -
如果若
index
位置上的元素值为 1,则说明是白色,就应该放在中间,不用管它,继续移动index
-
如果
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
四、动画理解(没有声音)
隐藏内容
此处内容需要权限查看