大家好,我是吴师兄。
今天分享的题目是 LeetCode 第 75 号问题:颜色分类。
这道题目可以很好的考察你对于快速排序的理解程度,所以考察的频率还挺高的。
同时,它也是一道中等题,做不出难题的情况下,做一做中等题压压惊吧。
还做不出来,那就刷刷 easy 题吧。
给定一个包含红色、白色和蓝色,一共 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
先不移动// 登录 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;
}
}