Sort colors系列
2024-10-11 16:04:45
75. Sort Colors
问题描述：
给一个包含n个数字的数组，其中有0,1,2；排序使得所有相同的数字相邻，且按照0,1,2的顺序。
思路：
（1）计数排序：
需要扫两遍数组，一遍统计个数，第二遍开始摆放数字。
代码如下：
void sortColors(vector<int>& nums) {
int i=,j=,k=;
int n=nums.size();
for(int p=;p<n;p++)
{
if(nums[p]==)
i++;
else if(nums[p]==)
j++;
else
k++;
}
for(int p=;p<n;p++)
{
if(p<i)
nums[p]=;
else if(p>=i&& p<i+j)
nums[p]=;
else
nums[p]=;
}
}
（2）如果只能扫一遍，很容易想到的就是左边存放0和1，右边存放2.两边往中间靠。
设置两个index，left记录第一个1的位置，left左边为0，right记录第一个非2的位置，right右边为2.
然后使用i从头到尾扫一遍，直到与right相遇。
i遇到0就换到左边去，遇到2就换到右边去，遇到1就跳过。
需要注意的是：由于left记录第一个1的位置，因此A[left]与A[i]交换后，A[left]为0,A[i]为1，因此i++；
而right记录第一个非2的位置，可能为0或1，因此A[right]与A[i]交换后，A[right]为2,A[i]为0或1，i不能前进，要后续判断。
由此该数组分为4段：[0,left)-->0; [left,i)-->1; [i,right]-->乱序; (right,n-1]-->2
0 0 0 1 1 1 2 1 0 2 1 2 2 2
^ ^ ^
left i right
最直接的方法就是partition方法，代码如下：
void sortColors(int A[], int n) {
int left = ;
int right = n-;
int i = ;
while(i <= right)
{
if(A[i] == )
{
swap(A[left], A[i]);
left ++;
i ++;
}
else if(A[i] == )
{
i ++;
}
else
{
swap(A[i], A[right]);
right --;
}
}
}
（3）最漂亮的一种做法：
【最直观：平移插入】
void sortColors(int A[], int n) {
int i = -;
int j = -;
int k = -;
for(int p = ; p < n; p ++)
{
//根据第i个数字，挪动0~i-1串。
if(A[p] == )
{
A[++k] = ; //2往后挪
A[++j] = ; //1往后挪
A[++i] = ; //0往后挪
}
else if(A[p] == )
{
A[++k] = ;
A[++j] = ;
}
else
A[++k] = ;
}
}
最新文章
- Programming Contest Problem Types
- 【转】 void与void*详解
- 2014 Super Training #4 E Paint the Grid Reloaded --联通块缩点+BFS
- tp空操作和空控制器处理
- Eclipse自动生成UML图（转载）
- Asp.net 后台添加Meta标签方法
- vs2013下使用Assist X的破解方法
- [TYVJ] P1001 第K极值
- Jquery如何获取控件ID
- window.settimeout用法与window.setInterval用法的区别
- 文件一键上传、汉字转拼音、excel文件上传下载功能模块的实现
- filebeat+logstash配置
- Nginx虚拟主机 子文件单独配置
- C语言小笔记
- 开源项目初涉（C++自我学习开始）
- Retrofit 2.0基于OKHttp更高效更快的网络框架 以及自定义转换器
- scala面向对象.高阶函数,柯里化,Actor编程简介
- Oracle NID工具修改数据库DBID、数据库名称、数据库实例名
- SQL 语句语法简介（一）
- GoogLeNet解读