【亡羊补牢】挑战数据结构与算法 第74期 LeetCode 75. 颜色分类(双指针)
发布日期:2021-06-29 14:34:52
浏览次数:2
分类:技术文章
本文共 1721 字,大约阅读时间需要 5 分钟。
仰望星空的人,不应该被嘲笑
题目描述
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。示例:
输入: [2,0,2,1,1,0]输出: [0,0,1,1,2,2]
进阶:
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗?来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-colors 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解题思路
双指针,当前值为2,那么就和右边指针进行交换,反之当前值为0,那么就和左边指针进行交换,为1就不动。
/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */var sortColors = function (nums) { let len = nums.length; let L = 0; let R = len - 1; let i = 0; while (i <= R) { while (nums[i] == 2 && i < R) { // 当前值为2,那么就和右边指针进行交换 [nums[i], nums[R]] = [nums[R], nums[i]]; R--; } while (nums[i] == 0 && i > L) { // 当前值为0,那么就和左边指针进行交换 [nums[i], nums[L]] = [nums[L], nums[i]]; L++; } i++; } return nums;};
我想下面这份代码应该会更好理解一点:
/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */var sortColors = function (nums) { let len = nums.length; let L = 0; let R = len - 1; let i = 0; while (i <= R) { if (nums[i] == 0) { // 当前值为0,那么就和左边指针进行交换 [nums[i], nums[L]] = [nums[L], nums[i]]; L++; i++; } else if (nums[i] == 2) { // 当前值为2,那么就和右边指针进行交换 [nums[i], nums[R]] = [nums[R], nums[i]]; R--; } else { i++; } } return nums;};
最后
文章产出不易,还望各位小伙伴们支持一波!
往期精选:
小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!
,方便小伙伴阅读玩耍~
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/108955036 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月30日 07时10分54秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
出行领域架构设计
2019-04-29
今日头条技术剖析
2019-04-29
聊聊微信微服务技术
2019-04-29
垂直电商架构进化之路
2019-04-29
1亿级PV网站架构演变
2019-04-29
揭秘大型网站架构进化之路
2019-04-29
浅谈 MySQL 集群高可用架构
2019-04-29
程序员职业规划
2019-04-29
2018,送给大家一份提升技术的宝典
2019-04-29
大型网站图片服务器架构的演进
2019-04-29
程序员黑话
2019-04-29
Web网站搭建从零到一
2019-04-29
一头扎进tomcat
2019-04-29
程序员该考虑什么时候辞职
2019-04-29
如果有一天程序员再也不忙了
2019-04-29
王兴成长之路
2019-04-29
靠纯技术是否能渡过中年危机
2019-04-29
Spring是怎样诞生的?
2019-04-29
互联网安全威胁及应对方案
2019-04-29
老程序员都去哪儿了?
2019-04-29