中国最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > php教程 > 【一天一道LeetCode】#75. Sort Colors

【一天一道LeetCode】#75. Sort Colors

来源:程序员人生   发布时间:2016-06-15 14:34:38 阅读次数:555次

1天1道LeetCode

本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处

(1)题目

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.

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?

(2)解题

题目大意:数组包括0,1,2,依照大小排列这些数字。

1、最简单的方法

利用STL的sort1句话就解决了。

class Solution { public: void sortColors(vector<int>& nums) { sort(nums.begin(),nums.end()); } };

2、两个指针

算法思想很简单,把所有的0交换到队首,把所有的1交换到队尾

class Solution { public: void sortColors(vector<int>& nums) { int start = 0; int end = nums.size()-1; for(int i = 0 ; i<nums.size();i++)//把0交换到前面 { if(nums[i]==0) { if(i!=start) swap(nums[i],nums[start]); start++; } } for(int i = nums.size()-1 ; i>=start ;i--)//把2交换到尾部 { if(nums[i]==2){ if(i!=end) swap(nums[i],nums[end]); end--; } } } };

3、两个指针优化版

保持3个指针i、j和k,从0~i表示1,i+1~j表示1,k~nums.size()表示2
代码也比较简单:

class Solution { public: void sortColors(vector<int>& nums) { int i = 0, j = i, k = nums.size() - 1; while(j <= k){ if(nums[j] == 0) swap(nums[i++], nums[j++]);//0交换到前面 else if(nums[j] == 1) j++;//1保持不动 else swap(nums[k--], nums[j]);//2交换到尾部 } } };
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生