【LeetCodeゼロブラシから】Sort Colors
タイトル:
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つのアイデアがあります.は速い列の思想に似ていて、2つのカーソルを設定します:startとend、1より小さいのはstartの位置に置いて、1より大きいのはendの位置に置いて、それから次第に中間に近づきます; は3つのカーソルを設定し、それぞれ0,1,2の開始位置をマークします.以上の方法とは異なり、移動しながら付与すると、新しい値と古い値の付与順序 が問題になる.
ここにはコードが貼られているブログがあります.http://www.cnblogs.com/ganganloveu/p/3703746.html
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.
回答:
グローバルソートといっても、実は同じ色の内部で、順序はまったく同じです.だから、知っておくべきことは、それぞれの色が最初に現れた位置だけです.
class Solution {
public:
void sortColors(vector<int>& nums) {
int len = nums.size();
int a = 0, b = 0, c = 0;
for(int i=0; i<len; i++)
{
if(nums[i] == 0) a++;
if(nums[i] == 1) b++;
if(nums[i] == 2) c++;
}
nums.clear();
for(int i=0; i<len; i++)
{
if(i < a) nums.push_back(0);
else if(i < (a+b)) nums.push_back(1);
else nums.push_back(2);
}
}
};しかし、この問題は終わっていません.もっと多くの要求があります.
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つのアイデアがあります.
ここにはコードが貼られているブログがあります.http://www.cnblogs.com/ganganloveu/p/3703746.html