[LeetCode] 75. Sort Colors

タイトルリンク:https://leetcode.com/problems/sort-colors/description/
Description
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.
問題を解く構想.
2つの変数red_nextとblue_prevを設定し、それぞれ赤色の次の位置と青色の前の位置を表す.次と前は相対配列の位置であり、配列の下付き1は2の前であり、2は1の後である.
まず配列の両端が順序を満たすようにフィルタリングし,中間が満たさない配列要素のみを考慮し,フィルタリング後の配列の下付きred_nextの前のすべての要素は0,blue_prevの後のすべての要素は2である.
そして、配列をred_nextからblue_prevまで遍歴し、赤色である値が0であることが判明すると、nums[red_next]と交換し、red_nextを加算することで、遍歴後のすべての赤色が配列の前部に配置される.
最後に、配列をblue_prevからred_nextまで繰り返し、青色の値が2であることが判明すると、nums[blue_prev]と交換し、blue_prevを減算することで、青色のものを配列の後部に配置する.
時間複雑度O(n),空間複雑度O(1)Code

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int red_next = 0;
        int blue_prev = nums.size() - 1;

        while (red_next < nums.size() && nums[red_next] == 0)
            red_next++;

        while (blue_prev >= 0 && nums[blue_prev] == 2)
            blue_prev--;

        for (int i = red_next; i <= blue_prev; ++i) {
            if (nums[i] == 0) {
                swap(nums[i], nums[red_next]);
                red_next++;
            }
        }

        for (int i = blue_prev; i >= red_next; --i) {
             if (nums[i] == 2) {
                swap(nums[i], nums[blue_prev]);
                blue_prev--;
            }
        }
    }
};