LeetCode75—颜色分类(java版)
2021/8/6 22:08:08
本文主要是介绍LeetCode75—颜色分类(java版),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述:
标签:数组 双指针 排序
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
代码:
思路分析:
其实这题最暴力的算法就是直接用api排序QAQ。不过真的太简单粗暴了。
这题主要是想考察快排的思想。比某个数小的在左边,等于某个数的在中间,大于某个数的在右边。还主要考察了“循环不变量”的思想。
1、要划分为三个区间
[0,zero)对应0
[zero,i)对应1
[two,len-1]对应2
所以需要定义三个指针zero,i(也就是one),two分别对应着0区间的右边界、1区间的右边界、2区间的左边界。可见从这个区间定义知道当i==two的时候循环停止。
2、为了保证初始化的时候 [0, zero) 为空,设置 zero = 0,所以要先交换再加加
3、为了保证初始化的时候 [two, len - 1] 为空,设置 two = len,所以要先减减再交换
class Solution { public void sortColors(int[] nums) { int len = nums.length; if(len < 2){ return; } int zero = 0; int i = 0; int two = len; while(i < two){ if(nums[i] == 0){ swap(nums,i,zero); i++; zero++; }else if(nums[i] == 1){ i++; }else{ two--; swap(nums,i,two); } } } public void swap(int[] nums,int index1,int index2){ int tmp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = tmp; } }
这篇关于LeetCode75—颜色分类(java版)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现