75.颜色分类

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

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

示例：

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

思路

1.可以在遍历整个数组的时候设置三个指针，p0表示下一个0应该存放的索引，p2表示下一个2应该存放的索引，cur表示当前遍历的元素的索引。
2.若num[cur]等于0，则交换cur和p0索引的元素，并将cur+1，p0+1。
3.若num[cur]等于2，则交货cur和p2索引的元素，并将p2-1，因为交换过来的元素可能为0，索引不能将cur+1。
4.若num[cur]等于1，直接将cur+1即可，无需处理。
5.当cur>p2的时候结束循环即可。

Java代码实现

    public void sortColors(int[] nums) {
         //用于表示下一个0应该被插入的位置
        int p0 = 0;

        //用于表示当前遍历元素的位置
        int cur = 0;

        //用于表示下一个2应该被插入的位置
        int p2 = nums.length-1;

        while(cur <= p2){
            if(nums[cur] == 0){
                swap(nums,p0,cur);
                p0++;
                cur++;
            }else if(nums[cur] == 2){
                swap(nums,cur,p2);
                p2--;
            }else{
                cur++;
            }
        }

    }

    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

Golang代码实现

func sortColors(nums []int)  {
    left,cur,right := 0,0,len(nums)-1

    for cur<=right{
        if nums[cur] == 1{
            cur++
        }else if nums[cur] == 0 {
            nums[cur],nums[left] = nums[left],nums[cur]
            left++
            cur++
        }else{
            nums[cur],nums[right] = nums[right],nums[cur]
            right--
        }
    }
}