注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex75 Sort Colors  

2015-05-18 22:06:16|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?



这一题太神了,我表示只会用简单的计数排序见c代码,直观,特别容易理解

void sortColors(int* nums, int numsSize) {
//相当于遍历了两遍,其实和题目的要求不太一样,题目要求,只遍历一遍
//而且需要常数空间分配
int num1, num2, num3, i;
num1 = num2 = num3 = 0;
for (i = 0; i<numsSize; i++)
{
if (nums[i] == 0) num1++;
if (nums[i] == 1) num2++;
if (nums[i] == 2) num3++;
}
int k = 0;
while (num1--) nums[k++] = 0;
while (num2--) nums[k++] = 1;
while (num3--) nums[k++] = 2;
}

网上有大神给的one -pass的算法,见c代码,已经做了一些注释了,应该比以前作者写的好懂多了~~

void sortColors1(int* nums, int numsSize)
{
int i = -1, j = -1, k = -1;

//我擦 这个方法吊炸天
//i j k分别用来指向 0 1 2最后排列的位置
for (int p = 0; p < numsSize; p++)
{
if (nums[p] == 0)
{
//如果是0的话,因可能已经出现了1和2了
//所以1 2的计数pointer都要往后挪一个位置
//必须先挪2 再挪1
//最后把0 方在i+1指向的位置
nums[++k] = 2;
nums[++j] = 1;
nums[++i] = 0;
}
else if (nums[p] == 1)
{
//如果是1的话,0就不管了,反正又不动
//直接挪后面一个2就可以了
nums[++k] = 2;
nums[++j] = 1;

}
else if (nums[p] == 2)
{
//如果是2的话就没有什么说的了直接附加到k+1的位置上
nums[++k] = 2;
}
}
}


参考
http://www.cnblogs.com/felixfang/p/3680047.html
  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017