Leetcode-75.颜色分类

发表于 分类于 阅读次数：

排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：双指针

思路：

构建两个指针p0,p2，p0表示下一个0应该放在的位置,p2表示下一个2应该放在的位置

1.curr指针遍历数组，当curr指向0时与p0指向位置元素进行交换,然后curr与p0都+1,

​ 注：curr指向0与p0交换后只有两种情况换到一个0或者一个1这种情况都应该让curr++

2.or当curr指向2与p2指向位置元进行交换，然后p2–然后继续判断该位置元素

3.curr指向1，则让curr++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void sortColors(vector<int>& nums) {
        
        int n=nums.size();
        int p0=0,p2=n-1,curr=0;
        while(curr<=p2)
        {
            if(nums[curr]==0)
                swap(nums[curr++],nums[p0++]);
            else if(nums[curr]==2)
                swap(nums[curr],nums[p2--]);
            else curr++;
        }
        return ;
    }
};