力扣hot100：75. 颜色分类（双指针）

本文主要是介绍力扣hot100：75. 颜色分类（双指针），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

75.颜色分类

本题是经典的「荷兰国旗问题」，由计算机科学家 Edsger W. Dijkstra 首先提出。

75. 颜色分类

在这里插入图片描述

1、遍历两遍

遍历两遍，第一遍放置0的位置，第二遍放置1的位置，我们只需要维护一个当前放置位置即可。
在这里插入图片描述

class Solution {
public:void sortColors(vector<int>& nums) {//扫描两遍，第一遍放好0的位置，第二遍放1int zero = 0;for(int i = 0; i < nums.size(); ++ i){if(nums[i] == 0){swap(nums[i], nums[zero ++]);}}//复用zerofor(int j = zero; j < nums.size(); ++ j){if(nums[j] == 1){swap(nums[j], nums[zero ++]);}}return;}
};

2、遍历一遍双指针

difficult to achieve

我们维护一个0的位置，并且维护一个1的位置：

确保1的位置不小于0的位置
当需要放入1时，直接加在当前指向需要放置的1的位置即可。
当需要放入0时，如果后面有1，这会打断1，不过，我们可以把这个1再插入1的位置即可。如果没有1直接放入

这种方法比较难写，情况有点多，实现起来比较复杂。由于时间复杂度差不多，因此推荐使用简单方法实现！

class Solution {
public:void sortColors(vector<int>& nums) {//扫描两遍，第一遍放好0的位置，第二遍放1int zero = 0;int one = 0;for(int i = 0; i < nums.size(); ++ i){//确保one在正确位置，情况分类比较难if(nums[i] == 1){swap(nums[i], nums[one ++]);}else if(nums[i] == 0){if(zero == one){swap(nums[zero ++], nums[i]);one ++;}else{if(zero < one && zero != 0){//0有数,1也有数swap(nums[one ++], nums[i]);nums[one - 1] = 1;nums[zero ++] = 0;}else{//0没数if(one != i){nums[zero ++] = 0;swap(nums[one], nums[i]);nums[one] = 1;}else{swap(nums[zero ++],nums[i]);}one++;}}}}return;}
};

3、双指针交换2的位置

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int p0 = 0, p2 = n - 1;for (int i = 0; i <= p2; ++i) {while (i <= p2 && nums[i] == 2) {swap(nums[i], nums[p2]);--p2;}if (nums[i] == 0) {swap(nums[i], nums[p0]);++p0;}}}
};