leetcode 75. Sort Colors 颜色分类

作者：okokabcd

2022 年 5 月 24 日
本文字数：1140 字
阅读完需：约 4 分钟

一、题目大意

链接：https://leetcode.cn/problems/sort-colors

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]输出：[0,1,2]

提示：

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

进阶：

你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

二、解题思路

两个思路，一是用桶排序，先统计频率，再按 key 排序，最后提取结果。另一种思路，因为值的话就 3 个是已经确定的，遍历数组 0 往数组最左边放，2 往最右边放，遍历完数组就排好了。

三、解题方法

3.1 Java 实现-桶排序

public class Solution {    public void sortColors(int[] nums) {        // 统计频率        Map<Integer, Integer> seqMap = new HashMap<>();        for (int tmp : nums) {            seqMap.put(tmp, seqMap.getOrDefault(tmp, 0) + 1);        }
        // 按key排序        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());        for (Map.Entry<Integer, Integer> entry : seqMap.entrySet()) {            priorityQueue.add(entry);        }
        // 提取结果        int idx = nums.length - 1;        while (!priorityQueue.isEmpty()) {            Map.Entry<Integer, Integer> entry = priorityQueue.poll();            for (int i = 0; i < entry.getValue(); i++) {                nums[idx--] = entry.getKey();            }        }    }}

复制代码

3.2 Java 实现-另一种思路

public class Solution2 {    public void sortColors(int[] nums) {        int left = 0;        int right = nums.length - 1;        // 注意结束条件是 i<=right        for (int i = 0; i <= right; i++) {            if (nums[i] == 0) {                swap(nums, i, left++);            } else if (nums[i] == 2) {                // 注意此时i要呆在原地，因为for里面会执行i++,此时做i--做消减                swap(nums, i--, right--);            }        }    }
    void swap(int[] nums, int i, int j) {        int tmp = nums[i];        nums[i] = nums[j];        nums[j] = tmp;    }}

复制代码

四、总结小记

2022/5/24 用固定的套路桶排序解题耗时 2 毫秒，用另一种思路耗时不到 1 毫秒，虽然耗时少但我们还要掌握固定套路。

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/9cd96454d4db8c74a315be586】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

还未添加个人简介

发布

暂无评论

创作场景