【数据结构与算法】颜色分类:三路快速排序算法思想实现
2021/9/2 1:06:27
本文主要是介绍【数据结构与算法】颜色分类:三路快速排序算法思想实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
颜色分类:三路快速排序算法思想实现
Java
https://leetcode-cn.com/problems/sort-colors/
解题思路
恰好三种元素,可以使用三路快速排序算法的思想,实现出来的时间复杂度是为O(n)级别的。首先是把元素区间分为3段,第一段存0,第二段存1,第三段存2。那么这样需要两个变量来指示这三个段的位置,约定:[0,tl) 为0,(tg,nums.length-1] 为2,[tl,i) 为1,[i,tg] 为未处理。那我们就可以写个while循环,[i,tg]未处理元素为空的时候退出循环,用i来遍历所有数据,遇到0放入区间[0,tl),放入时只需要i和tl位置的元素交换一下位置,tl右移一格就好了,同样的,遇到2放入(tg,nums.length-1]区间,也是交换一下位置,但是这时i不需要移动,因为根据定义[i,tg]中的为未处理元素,交换回来的tg处的元素是没有处理的,所以要进入下次循环处理一下,遇到1则直接i++就好了,因为约定[tl,i) 为1,i++就直接放入区间内了。遍历一遍之后数据也就都处理好处理完了,简单图示如下:
代码
class Solution { public void swap(int[] arr, int i,int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public void sortColors(int[] nums) { int i=0,tl = 0,tg = nums.length-1; // [0,tl) 为0,(tg,nums.length-1] 为2,[tl,i) 为1,[i,tg] 为未处理 while (i<=tg){ if(nums[i] == 0){ //放入0的部分 swap(nums,i,tl); tl++; i++; }else if(nums[i] == 1){ // 不动 i++; }else { swap(nums,i,tg); // 放入2的部分 tg--; } } } }
这篇关于【数据结构与算法】颜色分类:三路快速排序算法思想实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?