【leetcode】75. 颜色分类

题目内容

75. 颜色分类

思路分析

参考资料

方法一：单指针

可以采用一个单指针ptr，来表征“头部区域”的范围。遍历两遍数组：

第一遍：遇到0则将0放进“头部区域”，即交换nums[i]和nums[ptr]，并将ptr+1；
第二遍：遇到1则将1放进“头部区域”，即交换nums[i]和nums[ptr]，并将ptr+1。

经过这样的两遍遍历，即可把乱序的0，1，2数组重新排序好。

方法二：双指针

方法一要遍历两次数组，比较蠢，所以使用双指针来进行优化。

类似方法一，设两个指针。指针ptr0表示已排好序的0的范围，指针ptr1表示已排好序的0+已排好序的1的范围。

遍历一次数组：

如果遇到1则与方法一一样，交换并将ptr1+1;
如果遇到0则需要进行特殊处理。

当ptr1>ptr0时，表示已经排好序的0后有排好序的1，这时交换nums[i]和nums[ptr0]后，会把一个已经排好序的1换出去。因此需要再交换nums[i]（这时nums[i]已经变成了换出去的1）和nums[ptr1]。

当ptr1=ptr0时，表示已经排好序的0后没有排好序的1，不需要再做特殊处理。

不论ptr1>ptr0还是ptr1=ptr0，都需要将两个指针加1。

参考资料中的动图还不错，可以便于理解。

代码

#include <vector>
#include <math.h>
#include <limits.h>
#include <utility>

using namespace std;

// 【错误】面对[1,0,1]这种情况无能为力
// 双指针（快排思想）
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution1 {
public:
    void sortColors(vector<int>& nums) {
       int pivot = 1;
       
       int i{ 0 }; 
       int j = nums.size() - 1;

       while(i != j) {
          while (i < j && nums[j] > pivot) {
             j--;
          }
          while (i < j && nums[i] <= pivot) {
             i++;
          }
          
          int temp = nums[j];
          nums[j] = nums[i];
          nums[i] = temp;
       }

       for (int k = 0; k < nums.size(); ++k) {
          if (nums[k] == pivot) {
             nums[k] = nums[i];
             nums[i] = pivot;
             break;
          }
       }
    }
};

// 单指针
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution2 {
public:
    void sortColors(vector<int>& nums) {
       int n = nums.size();
       int ptr = 0;

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

       for (int i = 0; i < n; ++i) {
          if (nums[i] == 1) {
             swap(nums[i], nums[ptr]);
             ++ptr;
          }
       }
    }
};

// 双指针
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
    void sortColors(vector<int>& nums) {
       int n = nums.size();
       int ptr0 = 0, ptr1 = 0;

       for (int i = 0; i < n; ++i) {
          if (nums[i] == 0) {
             swap(nums[i], nums[ptr0]);
             if (ptr1 > ptr0) {
                swap(nums[i], nums[ptr1]);
             }
             ++ptr0;
             ++ptr1;
          } else if (nums[i] == 1) {
             swap(nums[i], nums[ptr1]);
             ++ptr1;
          }
       }

    }
};

int main() {
   Solution s;
   vector<int> input{ 2,0,2,1,1,0 };
   s.sortColors(input);
   int a = 0;
}

收获

一道题分几天做很恶心