一，顏色分類

1，問題簡述

給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列。

此題中，我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色。

進階：

你可以不使用代碼庫中的排序函數來解決這道題嗎？你能想出一個僅使用常數空間的一趟掃描算法嗎？

2，示例描述

示例 1：

輸入：nums = [2,0,2,1,1,0]
輸出：[0,0,1,1,2,2]
示例 2：

輸入：nums = [2,0,1]
輸出：[0,1,2]
示例 3：

輸入：nums = [0]
輸出：[0]
示例 4：

輸入：nums = [1]
輸出：[1]
 

提示：

n == nums.length
1 <= n <= 300
nums[i] 為 0、1 或 2

 

3，題解思路

基于雙指針的思路進行實現，基于鍵值對集合進行實現

4，題解程序

import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;

public class SortColorsTest2 {
    public static void main(String[] args) {
        int[] nums = {2, 0, 2, 1, 1, 0};
        sortColors(nums);
        System.out.println();
        for (int num : nums) {
            System.out.print(num + "\t");
        }
    }

    public static void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int left = 0;
        int right = nums.length - 1;
        for (int i = 0; i <= right; ) {
            if (nums[i] == 0) {
                int temp = nums[left];
                nums[left] = nums[i];
                nums[i] = temp;
                ++left;
                ++i;
            } else if (nums[i] == 2) {
                int temp = nums[right];
                nums[right] = nums[i];
                nums[i] = temp;
                --right;
            } else {
                ++i;
            }
        }
    }

    public static void sortColors2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        Arrays.sort(nums);
        Map<Integer, Integer> map = new LinkedHashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        Arrays.fill(nums, 0);
        int[] result = new int[nums.length];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer value = entry.getValue();
            while (value > 0) {
                result[index++] = entry.getKey();
                value--;
            }
        }
        System.arraycopy(result, 0, nums, 0, result.length);
    }
}