首页 > 其他 > 详细

sort color (荷兰国旗)

时间:2016-09-13 22:26:03      阅读:206      评论:0      收藏:0      [点我收藏+]

算法思想:

该问题是一个排序问题,可以将这个数组分为前部、中部、后部。这里的思路如下:将前部和后部的排在数组的前边和后边,中部的就自然排好了。设置三个指针:beginmidend,然后从mid的位置开始遍历。

1.如果遍历到的位置为0,则说明它属于前部,就将midbegin交换,然后midbegin前进。

2.如果遍历到的位置是1,则说明它属于中部,则只将mid前进。

3.如果遍历到的位置是2,则说明它属于后部,将midend交换,由于交换后mid的指向不确定,因此只将end--

void sortColors(vector<int>& nums) {
        int begin=0,end=nums.size()-1,mid=0;
        while(mid<=end&&begin<=mid){
            if(nums[mid]==0){
                swap(nums[mid],nums[begin]);
                begin++;
                mid++;
            }
            else if(nums[mid]==1)
                mid++;
            else if(nums[mid]==2){
                swap(nums[mid],nums[end]);
                end--;
            }
        }
}

 

sort color (荷兰国旗)

原文:http://www.cnblogs.com/healthylife/p/5869790.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!