LeetCode148|颜色分类

码农王同学

发布于 2021-01-15 10:56:25

2030

发布于 2021-01-15 10:56:25

文章被收录于专栏：后端Coder后端Coder

一，颜色分类

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