Leetcode skimming ---75

subject ： 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 .

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

Output ：[0,0,1,1,2,2]

Method 1 ： Single pointer

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)

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)

Spatial complexity ：O(1)

Method 3 ： Double pointer two

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i < n; ++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)

Spatial complexity ：O(1)