温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

LeetCode如何实现颜色分类

发布时间:2021-12-15 14:38:02 阅读:168 作者:小新 栏目:大数据
开发者测试专用服务器限时活动,0元免费领,库存有限,领完即止! 点击查看>>

这篇文章主要为大家展示了“LeetCode如何实现颜色分类”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“LeetCode如何实现颜色分类”这篇文章吧。

 

一,颜色分类

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.length1 <= n <= 300nums[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);    }}

以上是“LeetCode如何实现颜色分类”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

原文链接:https://my.oschina.net/u/3934278/blog/4865177

AI

开发者交流群×