题解 | #颜色分类#

方法1：

借助额外数据结构存储数据

import java.util.*;

public class Solution {
    public int[] sortColor(int[] colors) {
        int len = colors.length;
        // 三个集合，分别保存红白蓝元素（0-1-2）
        List<Integer> redList = new ArrayList<>();
        List<Integer> whiteList = new ArrayList<>();
        List<Integer> blueList = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            int val = colors[i];
            if (val == 0) {
                redList.add(val);
            } else if (val == 1) {
                whiteList.add(val);
            } else {
                // val == 2
                blueList.add(val);
            }
        }
        // 取出三个集合元素，合并成一个集合
        int[] resArray = new int[len];
        int redSize = redList.size();
        int whiteSize = whiteList.size();
        int blueSize = blueList.size();
        for (int i = 0; i < redSize; i++) {
            resArray[i] = redList.get(i);
        }
        for (int i = 0; i < whiteSize; i++) {
            resArray[i + redSize] = whiteList.get(i);
        }
        for (int i = 0; i < blueSize; i++) {
            resArray[i + redSize + whiteSize] = blueList.get(i);
        }
        return resArray;
    }
}

方法2：

双指针法

import java.util.*;

public class Solution {
    public int[] sortColor(int[] colors) {
        int len = colors.length;
        // 左指针遍历；碰到红色元素就和右指针交换，把红色元素放在前面
        int left = 0;
        int tempRight = left;
        while (tempRight < len) {
            if (colors[tempRight] == 0) {
                swap(colors, left, tempRight);
                left++;
            }
            tempRight++;
        }
        // 右指针遍历；碰到蓝色元素就和左指针交换，把蓝色元素放在后面
        int right = len - 1;
        int tempLeft = right;
        while (tempLeft >= 0) {
            if (colors[tempLeft] == 2) {
                swap(colors, right, tempLeft);
                right--;
            }
            tempLeft--;
        }
        return colors;
    }

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