leetcode 75.颜色分类（荷兰国旗题目）
题目形貌https://i-blog.csdnimg.cn/direct/3875f1ee3df64d9e968a1cb37e32027b.png
题目分析
本题是经典的「荷兰国旗题目」，由盘算机科学家 Edsger W. Dijkstra 起首提出。
要想单独解决这道题本身还是很简单的，统计0、1、2的数目然后按顺序赋值，或者手写一个冒泡排序，whatever。
但是在这一题中我们主要学习它的头脑，题目想要将一个数组分成三个区间，那么就要用到三指针法。时间复杂度O(n)。
在本文的末了会附上leetcode的双指针法，但是本文的主要目的就是学会三指针法，不管哪种方式，核心头脑是差不多的，本题的头脑同样也是快速排序中对于大量重复元素的优化方式，以致可以直接作为快排的核默算法。
解说算法原理
既然想要将一个数组分为0、1、2三个区域，那就界说三个指针来解决这个题目。
指针意义：
i 指向数组第一个元素的位置用来遍历数组
left 指向数组0区间末了一个元素
right 指向数组2区间第一个元素
整个数组在完成分区之后的指针位置分布是这样的，数组由三个部分字组成：
https://i-blog.csdnimg.cn/direct/561f88f3c2e745e1a504c3726f3bd4ea.png
注：x 为0区间末了一个元素， y 为2区间第一个元素
整个数组在正在分区的过程中时的指针位置分布是这样的，数组由四个部分组成：
https://i-blog.csdnimg.cn/direct/80c42af80a854bcba698675948147587.png
我们主要就是要研究正在分区时的指针分布，来规定循环条件以及各种操作。
数组在分区时分为四个区间：
从左到右依次是：0区间，1区间，待扫描区域，2区间
当待扫描区域消散后，数组分区就完成了
那么在最刚开始各个指针是怎么分布的呢？
以示例一为例：
nums =
指针的初始化
https://i-blog.csdnimg.cn/direct/07e86c594510468798cf8ab49e2ccffd.png
在最刚开始，数组并没有0区间和2区间，以是left指向数组第一个元素的左边位置，right指向数组的末了一个元素的右边位置，i指向数组的第一个元素。
i 指针扫描到不同数据的分类处理惩罚1
[*]当i扫描到0时，将i位置的元素与left + 1位置的元素交换，然后再left++，就将0放到了0区间中，末了再i++，准备扫描下一个元素。
Q：为什么不直接与left交换？
A：我们不能直接与left交换，因为left在刚开始是不在数组范围内的。我们是通过将left扩容的方式来涵盖0这个元素。
[*]当i扫描到2时，将i位置的元素与right - 1位置的元素交换，然后再right–，就将2放到了2区间中，此时i还不能急着++，因为新换过来的元素还没有扫描。就这样进入到下一次循环中，i会再处理惩罚这个新换来的元素。
[*]当i扫描到1时，直接i++，1就进入了1区间。
请添加图片形貌
https://i-blog.csdnimg.cn/direct/461c39e2d1b8413bb9061d912f0b6613.png
class Solution {
public:
void sortColors(vector<int>& nums) {
int left = -1,right = nums.size(); //left为0区间的最后一个元素位置，right为2区间的第一个元素位置
int i = 0; //i指针遍历整个数组
while(i < right) //,,,
{
if(nums == 0)
{
swap(nums,nums);
left++;i++;
}
else if(nums == 1) i++;
else
{
swap(nums,nums);
right--;
}
}
}
};
简写后：
class Solution {
public:
void sortColors(vector<int>& nums) {
int left = -1,right = nums.size(); //left为0区间的最后一个元素位置，right为2区间的第一个元素位置
int i = 0; //i指针遍历整个数组
while(i < right) //,,,
{
if(nums == 0) swap(nums,nums[++left]);
else if(nums == 1) i++;
else swap(nums,nums[--right]);
}
}
};
补充：
leetcode官方给出的双指针法也是经典的方法，在此引用供各人学习：
https://i-blog.csdnimg.cn/direct/525ac36f82b247609c8f8569558efbdd.png
https://i-blog.csdnimg.cn/direct/109d200e7a51496aa6d3cdc94c7906d3.gif
题解作者：力扣官方
题解链接：https://leetcode.cn/problems/sort-colors/solutions/437968/yan-se-fen-lei-by-leetcode-solution/
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]