75. Color classification (medium array double pointer sorting)

75. Color classification

Give one that contains red 、 White and blue 、 common n Array of elements nums , Sort them in place , Make elements of the same color adjacent , And follow the red 、 white 、 In blue order .

We use integers 0、 1 and 2 Red... Respectively 、 White and blue .

Must be in a library that does not use sort Function to solve this problem .

Example 1：

Input ：nums = [2,0,2,1,1,0]
Output ：[0,0,1,1,2,2]
Example 2：

Input ：nums = [2,0,1]
Output ：[0,1,2]

Tips ：

n == nums.length
1 <= n <= 300
nums[i] by 0、1 or 2

Advanced ：

Can you solve this problem without using the sort function in the code base ？
Can you come up with a one pass scanning algorithm using only constant space ？

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/sort-colors
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Take advantage of the fast-paced partition The second condition for the function idea to complete the advanced order .
Traversal array , With a double pointer zero and two Locate the end of the 0 and At the beginning 2（ Traverse it 2 Put them at the end in order ）. The traversal pointer variable is i, When you meet 0 The exchange zero and i The number at , take 0 In order to the beginning , When you meet 2, In exchange for two and i Number of places , take 2 Order to the end , encounter 1 direct i++ that will do .

Answer key （Java）

class Solution {
    
    public void sortColors(int[] nums) {
    
        int len = nums.length;
        if (len < 2) {
    
            return;
        }
        int i = 0, zero = 0, two = len;//two  It can also be initialized to len - 1
        while (i < two) {
    
            if (nums[i] == 0) {
    
                swap(nums, i, zero);
                zero++;
                i++;
            } else if (nums[i] == 1) {
    
                i++;
            } else {
    
                two--;
                swap(nums, i, two);
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
    
        if (index1 != index2) {
    
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }
}