荷兰国旗问题也是一个比较经典的问题，荷兰旗是由三色组成，每一种颜色都有自己单独的区域，三种颜色泾渭分明。抽象一点来说，也就是分成三区间的问题。下面是一道这个问题的经典题

75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:

不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]

输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。

首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。

你能想出一个仅使用常数空间的一趟扫描算法吗？

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/sort-colors

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

经典的解法是将遇到的0都放到链表的左边，遇到的2都放到链表的右边，然后1自然就都位于中间。

  1. class Solution {
  2. public:
  3.     void sortColors(vector<int>& nums) {
  5.         int end = nums.size() - 1;
  6.         if(end <= 0)
  7.             return;
  8.         int begin = 0;
  9.         int tmp;
  10.         for(int i = 0; i <= end;)
  11.         {
  12.             if(nums[i] == 0)
  13.             {
  14.                 tmp = nums[begin];
  15.                 nums[begin] = nums[i];
  16.                 nums[i] = tmp;
  17.                 begin++;
  18.                 i++;
  19.             }
  20.             else if(nums[i] == 2)
  21.             {
  22.                 tmp = nums[end];
  23.                 nums[end] = nums[i];
  24.                 nums[i] = tmp;
  25.                 end--;
  26.             }
  27.             else if(nums[i] == 1)
  28.             {
  29.                 i++;
  30.             }
  31.         }
  33.     }
  34. };

时间复杂度：由于对长度 N的数组进行了一次遍历，时间复杂度为O(N)。
空间复杂度 :由于只使用了常数空间，空间复杂度为O(1)。

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

        for(int i = 0; i < nums.size();)
        {
            if(nums[i] == 0)
            {
                nums[i] = nums[begin];
                nums[begin] = 0;
                begin++;
                i = begin;
            }
            else if(nums[i] == 2)
            {
                nums[i] = nums[end];
                nums[end] = 2;
                end--;
            }
            else
            {
                i++;
            }

            if(i > end)
                break;
        }
    }
};

还有一种解法是采用Hashmap的方法，不过相当于遍历了两次链表，同时还使用了额外的空间，唯一的好处是简单明了。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        map<int, int>count;

        for(auto &index : nums)
            count[index]++;

        int i = 0;
        for(auto &index : count)
        {
            while(index.second > 0)
            {
                nums[i] = index.first;
                index.second--;
                i++;
            }
        }

        return;
    }
};