75. Sort Colors.md

75. Sort Colors

Problem

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

tag:

• two pointers

Solution

通用的解法

通用的解法是遍历一次数组，统计各种颜色的个数，然后重写数组。该方法需要遍历两边数组，但能决绝超过三种颜色问题。

一次遍历

定义两个指针，分隔三种颜色， 一次遍历， 把第一种颜色移到数组最前面， 把第三种颜色移到最后面。

java

    public void sortColors(int[] nums) {
        int p1 = 0, p2 = nums.length-1;
        for(int i=0; i<=p2; ) {
            if(nums[i]==0) swap(nums, i++, p1++);
            else if(nums[i]==2) swap(nums, i, p2--);
            else i++;
        }
    }
    
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

go