LeetCode 第75题：颜色分类

给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排序。

使用整数0、1和2分布表示红色、白色和蓝色。

必须在不使用库内置sort函数的情况下解决这个问题。

示例1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2
• 进阶：你能想出一个仅使用常数空间的一趟扫描算法吗？

本题是经典的【荷兰国旗问题】，由计算机科学家 Edsger W. Dijkstra 首先提出。

解题思路：

方法一：单指针

两次遍历：在第一次遍历中，将数组中所有的0交换到数组头部。

                  第二次遍历中，将数组中所有的1交换到头部的0之后。

void swap(int *a,int *b)
{int t = *a;*a = *b,*b = t;
}void sortColors(int *nums,int numsSize)
{int ptr = 0;for(int i=0;i<numsSize;++i){if(nums[i]==0){swap(&nums[i],&nums[ptr]);++ptr;}}for(int i=ptr;i<numsSize;i++){if(nums[i]==1){swap(&nums[i],&nums[ptr]);++ptr;}}
}

 时间复杂度：O（n）,其中n是数组nums的长度。

 空间复杂度：O（1）

方法二：双指针

使用两个指针分别来交换0和1

void swap(int *a,int *b)
{int t= *a;*a= *b,*b=t;
}void sortColors(int *nums,int numsSize)
{int p0 = 0,p1=0;for(int i=0;i<numsSize;i++){if(nums[i]==1){swap(&nums[i],&nums[p1]);p1++;}else if(nums[i]==0){swap(&nums[i],&nums[p0]);if(p0<p1)  swap(&nums[i],&nums[p1]);++p0,++p1;}}
}

时间复杂度：O（n）,其中n是数组nums的长度

空间复杂度：O（1）

方法三：双指针

左指针P0来交换0

右指针P2来交换2

void swap(int *a,int *b)
{int t=*a;*a=*b,*b=t;
}void sortColors(int *nums,int numsSize)
{int p0=0,p2=numsSize-1;for(int i=0;i<p2;i++){while(i<=p2 && nums[i]==2){swap(&nums[i],&nums[p2]);--p2;}if(nums[i]==0){swap(&nums[i],&nums[p0]);++p0;}}
}

时间复杂度：O（n），其中n是数组nums的长度

空间复杂度：O（1）

方法四：记录0 1 2的个数，对其进行赋值即可。