75. Sort Colors

Description:

https://leetcode.com/problems/sort-colors/#/description

Algorithm:

1. Cheat…use three int to record the number of each color, and print them out. Time is fastest.
2. sort. Traverse the vector
   1. if (num[i] == 0) -> swap with the head element
   2. if (num[i] == 1 ) -> do nothing
   3. if (num[i] ==2 ) -> swap with the tail element

Code1:

class Solution {
public:
void sortColors(vector<int>& nums) {
int red = 0;
int white = 0;
int blue = 0;
for (int i = 0; i < nums.size();i++)
{
if (nums[i] == 0)
red++;
else if(nums[i] == 1)
white++;
else
blue++;
}
for (int i = 0; i < red; i++)
nums[i] = 0;
for (int i = red; i < red + white; i++)
nums[i] = 1;
for (int i = red+white; i < red + white + blue; i++)
nums[i] = 2;
}
};

Code2:

class Solution {
public:

void sortColors(vector<int>& nums)
{
int start = 0;
int mid = 0;
int end = nums.size()-1;

while(mid<=end)
{
if(nums[mid]==0)
{
nums[mid] = nums[start];
nums[start] = 0;
start++;
mid++;
}
else if(nums[mid]==1)
{
mid++;
}
else if(nums[mid] ==2)
{
nums[mid] = nums[end];
nums[end] = 2;
end--; // Here we don't need to change the mid
}
}
}
};

Timing:

1. Cheat: O(n)
2. Sort: O(n)