【Leetcode】75.颜色分类

news/2025/2/12 19:17:43
作者: 码蹄疾
毕业于哈尔滨工业大学。 小米广告第三代广告引擎的设计者、开发者;
负责小米应用商店、日历、开屏广告业务线研发;
主导小米广告引擎多个模块重构;
关注推荐、搜索、广告领域相关知识;

题目

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶:
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗?

题解

首先这个题目你肯定不能用数数的方法啊,如果你用了相当于说:“面试官傻逼!”
那怎么来解这种问题呢?我给大家说说一个不是那么绝对的经验,涉及到数组和链表的题目,先想想双指针法可不可以用
这个题目用三个指针:
index 表示当前遍历的元素
p1 记录最后一个0的位置
p2 记录最开始一个2的位置

然后从左到右便利,调整index、p1、p2元素

java版本

    public void sortColors(int[] nums) {// 1-passint p1 = 0, p2 = nums.length - 1, index = 0;while (index <= p2) {if (nums[index] == 0) {nums[index] = nums[p1];nums[p1] = 0;p1++;}if (nums[index] == 2) {nums[index] = nums[p2];nums[p2] = 2;p2--;index--;}index++;}}

python版本

class Solution:def sortColors(self, nums):""":type nums: List[int]:rtype: void Do not return anything, modify nums in-place instead."""p1 = 0p2 = len(nums) - 1index = 0while index <= p2:if nums[index] == 0:nums[index] = nums[p1]nums[p1] = 0p1 += 1if nums[index] == 2:nums[index] = nums[p2]nums[p2] = 2p2 -= 1index -= 1index += 1

热门文章

  • 【Leetcode】74. 搜索二维矩阵
  • 【Leetcode】73.矩阵置零
  • 【Leetcode】72.编辑距离

Leetcode名企之路


https://dhexx.cn/news/show-125725.html

相关文章

一招解决pip下载安装龟速的问题

一招解决pip下载安装龟速的问题&#xff0c;非常简单 使用镜像即可提速——超快 打开命令行 输入以下的命令 pip install xxx -i http://pypi.douban.com/simple/ --trusted-host pypi.douban.com注意&#xff0c;上面代码的xxx要换成你需要下载的模块名 然后点击回车&#…

为什么你的技术文章配图总是那么丑?那是你还没看过这篇教科书般的技术文章配图指南!...

这可能是一篇很多博客的读者都期待的文章&#xff0c;我最终还是决定说一说『如何为技术文章配图』这一话题&#xff0c;过去的几年一直都有非常多的读者在博客、微博和公众号下面提出这样的问题 —— 『你的图是用什么工具画的&#xff1f;』&#xff0c;对于这种问题我我一直…

使用思科4507交换机引擎上的万兆模块

解决前状态1、接口配置interface TenGigabitEthernet3/1description To C4507-387-standby-10Gswitchport mode trunkchannel-group 40 mode onend2、接口状态SW-SJHL-2C-386-Core#show interfaces tenGigabitEthernet 3/1TenGigabitEthernet3/1 is down, line protocol is dow…

一条命令升级pip

一条命令升级pip 超简单的 打开命令行 输入以下命令 点击回车&#xff08;Enter键&#xff09;即可 pip install --upgrade pip

vue项目实现返回不刷新、其他菜单进入刷新。keep-alive的用法

项目背景&#xff1a; 查询列表进入详情页&#xff0c;返回时列表页不刷新从其他菜单页进入查询列表&#xff0c;列表刷新实现 方案一&#xff1a;详情页通过模态窗口展示。方案二&#xff1a;详情页通过跳转&#xff0c;使用keep-alive处理。1.渲染组件配置 <keep-alive>…

langchain正式学习2

langchain正式学习2 接着上次 正式学习1看的那个handbook看 原文地址 : https://www.pinecone.io/learn/langchain-prompt-templates/ Prompt Engineering and LLMs with Langchain _ Pinecone Prompt Engineering and LLMs with Langchain 在传统的机器学习中&#xff0c;不…

史上最全的高性能代理服务器 Envoy 中文实战教程 !(强烈建议收藏)

什么是 EnvoyEnvoy 是一款 CNCF 旗下的开源项目&#xff0c;由 Lyft 开源。Envoy 采用 C 实现&#xff0c;是面向 Service Mesh 的高性能网络代理服务。它与应用程序并行运行&#xff0c;通过以平台无关的方式提供通用功能来抽象网络。当基础架构中的所有服务流量都通过 Envoy …

分享十个CSS3鼠标滑过文字动画特效

介绍10组基于CSS3的鼠标滑过文字动画特效&#xff0c;有上凸、下凹等文字动画。这些炫酷的CSS3文字效果可以让网页变得更加绚丽。效果图如下&#xff1a; 在线预览 源码下载 实现的代码。 html代码&#xff1a; <h2 class"headingOuter">Push down (shadow e…

操作系统期末考试重点知识

操作系统期末考试重点知识&#xff08;敲黑板&#xff01;&#xff01;&#xff01;&#xff09; 操作系统期末考试题型&#xff1a; &#xff08;1&#xff09;选择填空题 &#xff08;2&#xff09;简答题 &#xff08;3&#xff09;计算题 &#xff08;1&#xff09;选择填…

CentOS源码安装GitLab汉化版第3版

2019独角兽企业重金招聘Python工程师标准>>> 软件版本&#xff1a; 软件版本CentOS7.5GraphicsMagick1.3.31Git2.21.0Ruby2.5.3Go1.12Node.js10.15.2PostgreSQL11.2Redis5.0.3GitLab11.8.0 汉化版Nginx1.14.21. 安装依赖 yum -y install libicu-devel patch gcc-c r…