leetcode 75(原地单双指针）

本来这个题，看一眼上去就应该是sort排序（所以我写了一行sort直接Ａ了，，，）

实际这个题可以用移动指针的方法，，

首先看单指针：

单指针遍历两边，遇见了就换

 1 class Solution {
 2 public:
 3     void sortColors(vector<int>& nums) {
 4         int n = nums.size();
 5         int ptr = 0;
 6         for (int i = 0; i < n; ++i) {
 7             if (nums[i] == 0) {
 8                 swap(nums[i], nums[ptr]);
 9                 ++ptr;
10             }
11         }
12         for (int i = ptr; i < n; ++i) {
13             if (nums[i] == 1) {
14                 swap(nums[i], nums[ptr]);
15                 ++ptr;
16             }
17         }
18     }
19 };

时间复杂度Ｏ(nums.size())

空间复杂度Ｏ(1)

双指针（我觉得我不太适合写双指针orz,里面有很多需要注意的东西）

要注意p0,p1的含义

p0说明这个玩意之前是０

p1说明这个之前是１

你要明白如果你把0放好了，就不能再动了（因为0已经是搞在了最前面）

所以如果p0向后移动，p1也必须要一起移动

还有一个问题就是，p1在p0前面了，结果忽然遇见一个０

这个时候往往是这样：

前面一堆0然后第一个１标记为p1,后面是一堆1

这个时候i忽然遇见一个0，跟0交换的就是1了　

但实际上１　也已经是排好了的

所以这个时候没有办法，只能把原来的第一个1放到i的位置，然后把0放过来

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

总之，双指针的坑太多了啊啊啊啊！！！！！！