[LeetCode]75.颜色分类——题解(执行用时击败90% ,内存消耗击败 78%)

01

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

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

示例:

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

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

02

分析

显然，最直观的方法是通过一次遍历统计出0、1、2的个数，再按照0、1、2的顺序重写该数组。但该方法需要两次扫描。那有没有通过一次扫描就完成排列的方法呢？答案是：有！

问题1：思路是什么？

观察题目描述和题目示例的输出，0排在序列最前面，2排在序列最后面，因此，在扫描数组时，我们可以判断当前数字的值：

• 如果是0，就往数列前部移动；
• 如果是2，就往数列后部移动。

问题2：如何前移后移？

此时抛出另一个问题：往前部移动，移动到哪里呢？往后部移动，又移动到哪里呢？

——设置两个标记flag0和flag2。

开始时我们并不知道最终会有多少个0，但数列最前面一定是0，因此flag0初始值为数列最前面，即0；同样，开始时我们并不知道最终有多少个2，但数列最后面一定是2，所以flag2初始值为数组最后一个元素索引位置。初始化完毕后，接下来开始扫描过程（即更新标记flag0和flag2的过程）：

• 如果当前元素是0，将当前元素与索引为flag0的元素互换位置，flag0++；
• 如果当前元素是2，将当前元素与索引为flag2的元素互换位置，flag2--。

问题3：如果序列里没有0或者没有2呢？

如果序列里没有0，那么flag0始终指向数组第一个位置；同理，如果序列里没有2，flag2始终为数组最后一个元素索引位置。

问题4：如果当前元素为1，怎么处理？

不处理！为什么不处理呢？就因为有两个标记flag0和flag2的存在，因为两个标记严格限定了0和2的边界，自然而言，两个边界之间的就是1了。

03

代码

void swap(vector<int>& nums, int i, int j){
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}
 
void sortColors(vector<int>& nums) {
  //初始化标记
  int flag0 = 0;
  int flag2 = nums.size() - 1;
  for (int i = 0; i <= flag2; i++){
    if (nums[i] == 2){
      swap(nums, i, flag2);
      flag2--;
      i--;//之所以要i--，是因为交换到i处的值可能是0
    }
    else if (nums[i] == 0){
      swap(nums, i, flag0);
      flag0++;
    }
  }
}

复制

04

执行结果