[100天算法】-颜色分类(day 69)

news/2024/4/19 1:06:43

题目描述

给定一个包含红色、白色和蓝色,一共 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

伪代码

我们使用三个指针:left, mid, right (left <= mid <= right),数组元素可以分成四段,'[' 表示包括当前元素,'(' 表示不包括:- [0, left) 是 bottom 元素
- [left, mid) 是 middle 元素
- [mid, right) 是待分堆的元素
- [right, end] 是 top 元素遍历待分堆的元素,将它们归类:// 当 [mid, right) 这个区间没有元素时停止遍历
while mid <= right:if array[mid] < middle:swap(mid, left)left++ // 维护 bottom 元素的边界mid++ // 换过来的是一个 middle 元素,不需要继续分类,所以下一次循环从 mid + 1 开始归类else if array[mid] > middle:swap(mid, right)right-- // 维护 top 元素的边界// 换过来的元素原本在 [mid, right) 区间中,是一个待分堆元素,所以下一次循环还是从 mid 开始归类else:mid++// 当前是一个 middle 元素,不需要交换,只要将 mid 右移一步扩大 [left, mid) 这个区间就行

图解

75_0

复杂度

  • Time:$O(n)$,最多遍历一次数组,所以时间复杂度$O(n)$。
  • Space: O(1),直接在原数组上进行修改,没有用到额外空间,所以空间复杂度是 O(1)。

代码

JavaScript Code

/*** @param {number[]} nums* @return {void} Do not return anything, modify nums in-place instead.*/
var sortColors = function (nums) {const swap = (list, p1, p2) =>([list[p1], list[p2]] = [list[p2], list[p1]]);let red = 0,blue = nums.length - 1,p = 0;while (p <= blue) {switch (nums[p]) {case 0:swap(nums, red++, p);p++;break;case 1:p++;break;case 2:swap(nums, blue--, p);break;default:break;}}
};

Python Code

class Solution(object):def sortColors(self, nums):""":type nums: List[int]:rtype: None Do not return anything, modify nums in-place instead."""midKey = 1left, mid, right = 0, 0, len(nums) - 1while mid <= right:if nums[mid] < midKey:nums[mid], nums[left] = nums[left], nums[mid]mid += 1left += 1elif nums[mid] > midKey:nums[mid], nums[right] = nums[right], nums[mid]right -= 1else:mid += 1

http://www.ppmy.cn/news/1210099.html

相关文章

11月份 四川汽车托运报价已经上线

中国人不骗中国人!! 国庆小长假的高峰期过后 放假综合症的你还没痊愈吧 今天给大家整理了9条最新线路 广州到四川的托运单价便宜到&#x1f4a5; 核算下来不过几毛钱&#x1f4b0; 相比起自驾的漫长和疲惫&#x1f697; 托运不得不说真的很省事 - 赠送保险 很多客户第一次运车 …

大厂真题:【DP/贪心】字节跳动2023秋招-小红的 01 串

题目描述与示例 题目描述 小红拿到了一个 01 串&#xff0c;她准备将若干个字符1 染成红色&#xff0c;将若干个字符0 染成蓝色&#xff0c;但有个限制&#xff1a;如果一个0 和一个1 相邻&#xff0c;那么它们不能同时染色。 小红想知道&#xff0c;最多可以染多少个字符&a…

网络运维Day08

文章目录 克隆虚拟机修改网卡命名规则Linux配置IP地址 虚拟网络类型NAT模式隔离模式VMware-NAT模式 设置VMnet8网络模式为虚拟机自动配置IP地址 管理IP地址-ifconfig命令常用网络工具ip命令追踪路由ss命令ping命令 练习总结 克隆虚拟机 通过克隆技术&#xff0c;可以快速且方便…

粤嵌实训医疗项目--day06(Vue + SpringBoot)

往期回顾 粤嵌实训医疗项目(小组开发)--day05-CSDN博客粤嵌实训医疗项目--day04&#xff08;Vue SpringBoot&#xff09;-CSDN博客粤嵌实训医疗项目--day03&#xff08;Vue SpringBoot&#xff09;-CSDN博客粤嵌实训医疗项目day02&#xff08;Vue SpringBoot&#xff09;-CS…

WPS的JS宏基础(二)——其他

数据的输入和输出 InputBox(‘请输入内容’) //输入框 alert(‘a’) //简单消息框 MsgBox(‘b’) //进阶消息框 Debug.Print(‘c’) //立即窗口 Console.log(‘d’) //立即窗口 编写规则与注释 1.严格遵循大小写规范 2.每条语句之间用分号分隔 3.复合语句块&#xff08;块中…

定义无向加权图,并使用Pytorch_geometric实现图卷积

首先定义无向边并定义边的权重 import torch import torch.nn as nn from torch_geometric.nn import GCNConv import torch.nn.functional as F from torch_geometric.data import Dataa torch.LongTensor([0, 0, 1, 1, 2, 2, 3, 4]) b torch.LongTensor([0, 1, 2, 3, 1, 5,…

obs whip 100ms端到端时延 webrtc验证

obs----whip---->媒体服务-----whep-----→chrome播放器&#xff08;webrtc demo&#xff09; 所有软件在同一台机器 1&#xff09;h264251080p 平均时延&#xff1a;162.8ms 采样点ms&#xff1a;167151168169151168166168167153 2&#xff09;h264301080p 平均时延&…

LeetCode【215】数组中第k大的元素

题目&#xff1a; 思路&#xff1a; https://zhuanlan.zhihu.com/p/59110615 代码&#xff1a; public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> queue new PriorityQueue<>((o1, o2) -> o1 - o2);for (int i 0; i < nums.lengt…

WPF中ElementName与RelativeSource绑定的局限性以及对策

完全来源于十月的寒流&#xff0c;感谢大佬讲解 <Window x:Class"Test_01.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schem…

Go开发基础环境搭建

前面&#xff0c;我们写了下关于GO的入门简介&#xff0c;今天我们打算实操&#xff0c;在实操之前需要准备下基础环境。 IDE开发工具 GoLand 是一款由捷克软件开发公司 JetBrains 专为 Go 开发的跨平台商业 IDE。Goland 具有 Strong Code Insight、Navigation & Search、…

Python使用腾讯云SDK实现对象存储(上传文件、创建桶)

文章目录 1. 开通服务2. 创建存储桶3. 手动上传文件并查看4. python上传文件4.1 找到sdk文档4.2 初始化代码4.3 region获取4.4 secret_id和secret_key获取4.5 上传对象代码4.6 python实现上传文件 5 python创建桶 首先来到腾讯云官网 https://cloud.tencent.com/1. 开通服务 来…

【我悟了】异常断电导致的文件系统变为只读——案例分析

背景 应领导要求&#xff0c;临时支持其他项目上遇到的一个问题。由于该问题属于未涉及的知识领域&#xff0c;从接触到最终给出方案&#xff0c;也花了我不少精力。在此进行分享&#xff0c;主要介绍在面对不熟悉的问题领域时&#xff0c;分析问题的思路。希望能够给年轻的同学…

Harbor2.9.1安装文件及源码

github上下载相关文件速度实在是太慢了&#xff0c;几百M的文件下载了几个小时。 保存到网盘里面&#xff0c;阿里云盘不支持普通格式压缩文件的分享&#xff0c;保存成.exe格式&#xff0c;下载后就解压文件打开解压。 包含“Harbor2.9.1离线安装文件”、“Harbor2.9.1在线安装…

【chat】4: ubuntu20.04:数据库创建:mysql8 导入5.7表

【chat】3: ubutnu 安装mysql-8 并支持远程访问 已经支持 8.0的SQLyog 远程访问:大神2021年的文章:sql是5.7的版本,我使用的ubuntu20.04,8.0版本:chat数据库设计 C++搭建集群聊天室(七):MySQL数据库配置 及项目工程目录配置 User表,以id 唯一标识 Friend 表,自己的id…

HTML点击链接强制触发下载

常见网页中会有很多点击链接即下载的内容&#xff0c;以下示范一下如何实现 <a href"文件地址" download"下载的文件名字&#xff08;不包括后缀&#xff09;">强制下载</a> 下面举个例子&#xff1a; <a href"./image/test.jpg"…

❤ Uniapp使用 ( 三 配置和各种使用篇)

❤ Uniapp使用 ( 三 配置和各种使用篇) 1、 uniapp引入 vant 引入方式 1、下载vant源码 方式一&#xff1a;从 Vant 官网首页进入 GitHub下载对应版本的压缩包,将文件解压后备用,确保下载的压缩包里有dist 文件夹 2、创建 uniapp 项目,在根目录下新建 一个文件夹wxcomponent…

启动Docker服务后显示Docker Engine stopped

1、重新启动Docker服务&#xff1a;打开Windows服务管理器&#xff08;可以在开始菜单中搜索&#xff09;&#xff0c;找到"Docker Desktop Service"或类似命名的服务&#xff0c;右键单击并选择"重启"。稍等片刻&#xff0c;看看是否重新启动成功 2、尝试…

【2】Spring Boot 3 项目搭建

目录 【2】Spring Boot 3 初始项目搭建项目生成1. 使用IDEA商业版创建2. 使用官方start脚手架创建 配置与启动Git版本控制 个人主页: 【⭐️个人主页】 需要您的【&#x1f496; 点赞关注】支持 &#x1f4af; 【2】Spring Boot 3 初始项目搭建 项目生成 1. 使用IDEA商业版创…

深度学习之pytorch第一课

学习使用pytorch&#xff0c;然后进行简单的线性模型的训练与保存 学习代码如下&#xff1a; import numpy as np import torch import torch.nn as nn x_value [i for i in range(11)] x_train np.array(x_value,dtypenp.float32) print(x_train.shape) x_train x_train.r…

RT-Thread Env使用

Env用户手册 Env是RT-Thread推出的开发辅助工具&#xff0c;针对基于RT-Thread操作系统的项目工程&#xff0c;提供编译构建环境、图形化系统配置及软件包管理功能。 其内置的menuconfig提供了简单易用的配置裁剪工具&#xff0c;可对内核、组件和软件包进行自由裁剪&#xf…