leetcode 75. 颜色分类

leetcode

1. 数组标记法
   C++：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        
        std::vector<int> arrMarks = std::vector<int>(3, 0);
        for ( int i = 0; i < nums.size(); ++i ) {

            int value = nums[i];
            if ( value < arrMarks.size() ) {

                arrMarks[value] += 1;
            }
        }

        std::vector<int> sortedNums;
        for ( int i = 0; i < arrMarks.size(); ++i ) {

            for ( int j = 0; j < arrMarks[i]; ++j ) {

                sortedNums.push_back(i);
            }
        }

        nums = sortedNums;
    }
};

2. 三指针
   C++：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        
        int left = 0;
        int right = nums.size() - 1;
        int current = left;
        while ( current <= right ) {

            if ( nums[current] == 0 && current >= left ) {

                std::swap(nums[current], nums[left]);
                ++left;

            } else if ( nums[current] == 2 ) {

                std::swap(nums[current], nums[right]);
                --right;

            } else {

                ++current;
            }
        }
    }
};

3. 双指针法
   C++：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        
        int left = 0;
        int right = nums.size() - 1;
        for ( int i = 0; i <= right; ++i ) {

            while ( i <= right && nums[i] == 2 ) {

                std::swap(nums[i], nums[right]);
                --right;
            }

            if ( nums[i] == 0 ) {

                std:;swap(nums[i], nums[left]);
                ++left;
            }
        }
    }
};