1008 color classification

The title is as follows

Give one that contains red 、 White and blue 、 common n Array of elements nums , Sort them in place , Make elements of the same color adjacent , And follow the red 、 white 、 In blue order .

We use integers 0、 1 and 2 Red... Respectively 、 White and blue .

Must be in a library that does not use sort Function to solve this problem .

Example 1：
Input ：nums = [2,0,2,1,1,0]
Output ：[0,0,1,1,2,2]

Example 2：
Input ：nums = [2,0,1]
Output ：[0,1,2]

Their thinking

Method 1 ： Single pointer

Ideas and algorithms

We can consider traversing the array twice . In the first traversal , We'll take all the... In the array 0 Swap to the head of the array . In the second pass , We'll take all the... In the array 1 Switched to head 0 after . here , be-all 2 All appear at the end of the array , So we're done sorting .

In particular , We use a pointer ptr Express 「 Head 」 The scope of the ,ptr An integer is stored in , Represents an array nums From the position 0 To the position ptr−1 All belong to 「 Head 」.ptr The initial value of 0, It means that no number is in 「 Head 」.

In the first traversal , We traverse the entire array from left to right , If you find it 0, So you're going to have to 0 And 「 Head 」 The elements of position are exchanged , And will 「 Head 」 Expand one position backward . After traversal , be-all 0 All exchanged 「 Head 」 The scope of the , also 「 Head 」 Contains only 0.

In the second pass , We from 「 Head 」 Start , Traverse the entire array from left to right , If you find it 1, So you're going to have to 1 And 「 Head 」 The elements of position are exchanged , And will 「 Head 」 Expand one position backward . After traversal , be-all 1 All exchanged 「 Head 」 The scope of the , And they're all there 0 after , here 2 Only in 「 Head 」 Outside the location , So the sorting is complete .

class Solution 
{
    
public:
    void sortColors(vector<int>& nums) 
    {
    
        int n = nums.size();
        int ptr = 0;
        for (int i = 0; i < n; ++i) 
        {
    
            if (nums[i] == 0) 
            {
    
                swap(nums[i], nums[ptr]);
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) 
        {
    
            if (nums[i] == 1) 
            {
    
                swap(nums[i], nums[ptr]);
                ++ptr;
            }
        }
    }
};

Complexity analysis
Time complexity ：O(n), among n It's an array nums The length of .
Spatial complexity ：O(1).

Method 2 ： Double pointer

class Solution 
{
    
public:
    void sortColors(vector<int>& nums)
    {
    
        int n = nums.size();
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) 
        {
    
            if (nums[i] == 1) 
            {
    
                swap(nums[i], nums[p1]);
                ++p1;
            }
            else if (nums[i] == 0) 
            {
    
                swap(nums[i], nums[p0]);
                if (p0 < p1)
                {
    
                    swap(nums[i], nums[p1]);
                }
                ++p0;
                ++p1;
            }
        }
    }
};

Complexity analysis
Time complexity ：O(n), among nn It's an array nums The length of .
Spatial complexity ：O(1).

Method 3 ： Double pointer

class Solution 
{
    
public:
    void sortColors(vector<int>& nums) 
    {
    
        int n = nums.size();
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i)
        {
    
            while (i <= p2 && nums[i] == 2) 
            {
    
                swap(nums[i], nums[p2]);
                --p2;
            }
            if (nums[i] == 0) 
            {
    
                swap(nums[i], nums[p0]);
                ++p0;
            }
        }
    }
};

Complexity analysis
Time complexity ：O(n), among nn It's an array nums The length of .
Spatial complexity ：O(1)