1. 题目解析
题目链接:75. 颜色分类
这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。
2.算法原理
算法思路解析
本算法采用三指针法,将数组划分为三个区域,分别用于存放值为0、1和2的元素。通过精心设计的指针移动策略,算法能够在单次遍历中完成数组的重新排序。
定义与初始化
nums
:待排序的数组,长度为n
。left
:指向0序列的末尾,初始化为-1。cur
:当前扫描的数组位置,初始化为0。right
:指向2序列的起始位置,初始化为n
。
区间保证
在算法执行过程中,始终保证以下区间划分:
[0, left]
:存放值为0的元素。[left + 1, cur - 1]
:存放值为1的元素。[cur, right - 1]
:待处理的元素区间。[right, n - 1]
:存放值为2的元素。
算法流程
-
初始化指针:设置
cur = 0
,left = -1
,right = n
。 -
遍历数组:当
cur < right
时,循环执行以下步骤:a. 处理值为0的元素:
- 若
nums[cur] == 0
,则将nums[cur]
与nums[left + 1]
交换,使0元素移至正确位置。 - 更新
left
指针,left++
。 - 更新
cur
指针,cur++
。
b. 处理值为1的元素:
- 若
nums[cur] == 1
,则无需交换,直接更新cur
指针,cur++
。
c. 处理值为2的元素:
- 若
nums[cur] == 2
,则将nums[cur]
与nums[right - 1]
交换,使2元素移至右侧区域。 - 更新
right
指针,right--
。 - 注意此时不更新
cur
指针,因为交换过来的元素尚未处理。
- 若
-
循环结束后的区间:
[0, left]
区间存放了所有值为0的元素。[left + 1, right - 1]
区间存放了所有值为1的元素。[right, n - 1]
区间存放了所有值为2的元素。
3.代码编写
class Solution
{
public:
void sortColors(vector<int>& nums)
{
int left = -1, right = nums.size(), i = 0;
while(i < right)
{
if(nums[i] == 0)
{
swap(nums[++left], nums[i++]);
}
else if(nums[i] == 1)
{
i++;
}
else
{
swap(nums[--right], nums[i]);
}
}
}
};
The Last
嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。
觉得有点收获的话,不妨给我点个赞吧!
如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~