75. Sort Colors

时间：2017-02-05 12:23:16 阅读：124 评论：0 收藏：0 [点我收藏+]

Problem Statement:

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?

Solutions

Solution one: two pass

First, we keep three counters to record the number of red, white, and blue.
Then, loop to enumerate all the elements in array and update the counter.
Finally, we set the value of nums according to the value of three counters.

 1 void sortColors(vector<int>& nums) {
 2         int red_cnt = 0, white_cnt = 0, blue_cnt = 0;
 3         
 4         // count the number of red, white, and blue individually
 5         for(vector<int>::size_type ix = 0; ix < nums.size(); ix++){
 6             switch(nums[ix]){
 7                 case 0:
 8                     red_cnt++;
 9                     break;
10                 case 1:
11                     white_cnt++;
12                     break;
13                 case 2:
14                     blue_cnt++;
15                     break;
16                 default:
17                     break;
18             }
19         }
20         // set red to 0
21         for(vector<int>::size_type ix = 0; ix < red_cnt; ix++){
22             nums[ix] = 0;
23         }
24         // set white to 1
25         for(vector<int>::size_type ix = red_cnt; ix < red_cnt + white_cnt; ix++){
26             nums[ix] = 1;
27         }
28         // set blue to 2
29         for(vector<int>::size_type ix = red_cnt + white_cnt; ix < red_cnt + white_cnt + blue_cnt; ix++){
30             nums[ix] = 2;
31         }
32         return;
33     }

Solution two: one pass

We keep two pointer, one is named low, which points to the start position of the array, another is named high, which points to the last element of the array.
Second, we enumerate the array one time:
- if current element is red(0), swap current element with nums[low], meanwhile low++
- if current element is blue(2), swap current element with nums[high], meanwhile high--
Then we get the sorted array

 1 void sortColors(vector<int>& nums) {
 2         if(nums.empty()){
 3             return;
 4         }
 5         
 6         // the type of low and high should be int
 7         // since high should minus one
 8         // it could be negative value
 9         int ix = 0, low = 0, high = nums.size() - 1, temp;
10         
11         while(ix <= high){
12             switch(nums[ix]){
13                 case 0:
14                     temp = nums[low];
15                     nums[low] = nums[ix];
16                     nums[ix] = temp;
17                     low++;
18                     // increase the pointer when swap an element with low
19                     ix++;
20                     break;
21                 case 2:
22                     temp = nums[high];
23                     nums[high] = nums[ix];
24                     nums[ix] = temp;
25                     high--;
26                     // do not increase the pointer when swap an element with low
27                     // we need check the element just swap from end
28                     break;
29                 default:
30                     ix++;
31                     break;
32             }
33         }
34         return;
35 }

75. Sort Colors

原文：http://www.cnblogs.com/wdw828/p/6367149.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)