【Leetcode每日一题】 分治 - 颜色分类（难度⭐⭐）（57）

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的元素。

算法流程

1. 初始化指针：设置cur = 0，left = -1，right = n。

2. 遍历数组：当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指针，因为交换过来的元素尚未处理。

3. 循环结束后的区间：

   • [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

嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。

觉得有点收获的话，不妨给我点个赞吧！

如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~