leetcode刷题-75颜色分类
2024-08-28 11:28:40
题目
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
思路
基本思路:首先,计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
荷兰三色旗问题:设置三个指针p0,p2,cur来分别追踪0的最右边界,2的最左边界和当前考虑的元素。
当cur<=p2时:若nums[cur]=0,则交换p0和cur,其两个指针都向后一位,若nums[cur]=2,则交换p2和cur,p2向前一位,若nums[cur]=1,则cur指针向前一位
实现
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
p0 = 0
p2 = len(nums) - 1
cur = 0
while cur <= p2:
if nums[cur] == 0:
nums[p0], nums[cur] = nums[cur], nums[p0]
p0 += 1
cur += 1
elif nums[cur] == 2:
nums[p2], nums[cur] = nums[cur], nums[p2]
p2 -= 1
else:
cur += 1
最新文章
- php 判断是手机版还是电脑端
- SPJS Upload for SharePoint: Custom upload page for uploading documents to various document libraries in a site collection
- 缓存插件 EHCache 页面缓存CachingFilter
- leetcode 102 Binary Tree Level Order Traversal ----- java
- Codeforces 665D Simple Subset [简单数学]
- CTSC2016&;&;APIO2016游记
- DevExpress 用户控件 分页(上)
- python进阶之路4.2---装饰器
- Hdu 1404 Digital Deletions
- 与众不同 windows phone (5) - Chooser(选择器)
- 聊聊高并发(三十八)解析java.util.concurrent各个组件(十四) 理解Executor接口的设计
- sql server DateTime相关内置函数总结
- IIS部署Angular2
- ActiveMQ组件使用方法
- javascript进阶笔记(2)
- 洛谷P3953 逛公园 [noip2017] 图论+dp
- 关于文章cisco漏洞4786
- HwUI,CMS管理系统模板,漂亮,简单,兼容好
- python 去除不可见的控制字符
- R的数据库访问-MySQL
热门文章
- Prometheus Operator 教程:根据服务维度对 Prometheus 分片
- Java—API/Obiect类的equals toString方法/String类/StringBuffer类/正则表达式
- leetcode 877. Stone Game 详解 -——动态规划
- 源代码管理工具 ——Git的介绍与简要教程
- vue element Admin - 修改浏览器标签名 + 添加tagView标签 +固定导航头部 + 添加侧边栏Logo
- 如何校验内存数据的一致性,DynamicExpresso 算是帮上大忙了
- 国人开源了一款超好用的 Redis 客户端,真香!!
- StructuredStreaming(New)
- Dubbo系列之 (五)服务订阅(2)
- Azure Kubernetes Service 入门