LeetCode如何實(shí)現(xiàn)顏色分類

一，顏色分類

1，問題簡(jiǎn)述

給定一個(gè)包含紅色、白色和藍(lán)色，一共 n 個(gè)元素的數(shù)組，原地對(duì)它們進(jìn)行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍(lán)色順序排列。

此題中，我們使用整數(shù) 0、 1 和 2 分別表示紅色、白色和藍(lán)色。

進(jìn)階：

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

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，題解思路

基于雙指針的思路進(jìn)行實(shí)現(xiàn)，基于鍵值對(duì)集合進(jìn)行實(shí)現(xiàn)

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);
   }
}