LeetCode(31) 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如,
arr = [1,2,3]
,以下这些都可以视作arr
的排列:[1,2,3]
、[1,3,2]
、[3,1,2]
、[2,3,1]
。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。
- 例如,
arr = [1,2,3]
的下一个排列是[1,3,2]
。 - 类似地,
arr = [2,3,1]
的下一个排列是[3,1,2]
。 - 而
arr = [3,2,1]
的下一个排列是[1,2,3]
,因为[3,2,1]
不存在一个字典序更大的排列。
给你一个整数数组 nums
,找出 nums
的下一个排列。
必须 原地 修改,只允许使用额外常数空间。
示例 1:
输入:nums = [1,2,3] 输出:[1,3,2]
示例 2:
输入:nums = [3,2,1] 输出:[1,2,3]
示例 3:
输入:nums = [1,1,5] 输出:[1,5,1]
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 100
思路:
先找出最大的索引 k 满足 nums[k] < nums[k+1],如果不存在,就翻转整个数组;
再找出另一个最大索引 l 满足 nums[l] > nums[k];
交换 nums[l] 和 nums[k];
最后翻转 nums[k+1:]
nums = [1,2,7,4,3,1],
-
第一步: 倒序遍历数组, 找出第一组: 前一个数比后一个数小的两个数, 即[2, 7]
-
2所处的这个位置就是需要找出比它稍微大的数的位置
-
我们从[7,4,3,1]中找出比2大的数中的最小值, 也就是3, 找到后跟2交换即可;nums = [1,3,7,4,2,1]; 当然了, 如果没找到的话, 直接跳到第4步, 直接升序排列输出
-
对3后面的数, 升序排列, 即最终结果: nums = [1,3,1,2,4,7]
时间复杂度:O(n) 空间复杂度:O(1)
Java代码
class Solution {public void nextPermutation(int[] nums) {if (nums == null || nums.length == 0) return;int firstIndex = -1;for (int i = nums.length - 2; i >= 0; i--) {if (nums[i] < nums[i + 1]) {firstIndex = i;break;}}if (firstIndex == -1) {reverse(nums, 0, nums.length - 1);return;}int secondIndex = -1;for (int i = nums.length - 1; i >= 0; i--) {if (nums[i] > nums[firstIndex]) {secondIndex = i;break;}}swap(nums, firstIndex, secondIndex);reverse(nums, firstIndex + 1, nums.length - 1);return;}private void reverse(int[] nums, int i, int j) {while (i < j) {swap(nums, i++, j--);}}private void swap(int[] nums, int i, int i1) {int tmp = nums[i];nums[i] = nums[i1];nums[i1] = tmp;}
}
相关文章:
LeetCode(31) 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如,arr [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地…...
Git LFS: 简单高效的大文件版本控制
Git Large File Storage 问题 在使用git上传大文件时候,git push时候会报错: remote: error: File xxx.tar.gz is 135.17 MB; this exceeds GitHubs file size limit of 100 MB可以看到,git限制上传大小是100MB,超过的话就会报错ÿ…...
如何培养用户思维
产品开发是根据用户要求建造出系统的过程,产品开发是一项包括需求捕捉、需求分析、设计、实现和测试的系统工程,一般通过某种程序设计语言来实现。然而用户思维能够帮助企业更好地理解市场需求,进行产品的开发和完善,用户是企业产…...
由浅入深理解C#中的事件
目录 本文较长,给大家提供了目录,可以直接看自己感兴趣的部分。 前言有关事件的概念示例 简单示例 标准 .NET 事件模式 使用泛型版本的标准 .NET 事件模式 补充总结 参考前言 前面介绍了C#中的委托,事件的很多部分都与委托…...
Nginx(十六) 配置文件详解 - server stream服务流
本篇文章主要讲 ngx_stream_core_module 模块下各指令的使用方法,Nginx默认未配置该模块,需要用“--with-stream”配置参数重新编译Nginx。 worker_processes auto;error_log /var/log/nginx/error.log info;events {worker_connections 1024; }stream…...
Css中默认与继承
initial默认样式: initial 用于设置 Css 属性为默认值 h1 {color: initial; }如display或position不能被设置为initial,因为有默认属性。例如:display:inline inherit继承样式: inherit 用于设置 Css 属性应从父元素继承 di…...
gitee上的vue大屏项目
在 Gitee 上,有几个值得注意的 Vue 大屏项目:vue-big-screen-plugin (Gitee): 这是一个基于 Vue3、Typescript、DataV 和 ECharts5 框架的可视化大屏项目。它使用 .vue 和 .tsx 文件构建界面,并采用新版动态屏幕适配方案。这个项目支持数据的动态刷新渲染,内部的 DataV 和 …...
【LeetCode:114. 二叉树展开为链表 | 二叉树 + 递归】
🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,…...
社保养老金发放计算方法
退休后养老金计算公式很复杂,自己自行百度查一下,这里说一下男性,女工人,女干部之间计算差别。 退休后,能到手的养老金多少,取决于你的个人账户里的钱,个人账户里的钱越多,到手养老…...
概率论基础复习题
一、填空题 二、选择题 答案:B 答案:C 答案:C 答案:D。统计量不含任何未知参数。 答案:A 答案:C 样本均值是总体均值的无偏估计;样本方差是总体方差的无偏估计。 答案:B。统计值是一…...
c++,mutex,unique_lock,recursive_mutex,shared_mutex对比分析
当处理多线程并发时,正确使用锁是确保线程安全的关键。 1. std::mutex(互斥锁): std::mutex 是C标准库提供的最基本的锁。它的基本使用如下: #include <iostream> #include <mutex> #include <threa…...
MySQL与Oracle数据库在网络安全等级方面用到的命令
MySQL数据库命令集 查看数据库版本 SELECT VERSION(); 空口令查询 SELECT user,host,account_locked FROM mysql.user WHERE user ; SELECT * FROM mysql.user; 查询 用户的密码加密情况 SELECT HOST,USER,PLUGIN FROM mysql.user; 查询是否有空用户 SELECT host,user,plug…...
MySQL——视图
目录 一.视图介绍 二.基本使用 三.视图规则和限制 一.视图介绍 视图是一个虚拟表,其内容由查询定义。同真实的表一样,视图包含一系列带有名称的列和行数据。视图的数据变化会影响到基表,基表的数据变化也会影响到视图。 二.基本使用 创…...
【响应式编程-03】Lambda表达式底层实现原理
一、简要描述 Lambda的底层实现原理Lambda表达式编译和运行过程 二、Lambda的底层实现原理 Lambda表达式的本质 函数式接口的匿名子类的匿名对象 反编译:cfr-0.145.jar 反编译:LambdaMetafactory.metafactory() 跟踪调试,转储Lambda类&#x…...
深入理解可变参数
1.C语言方式 目录 1.C语言方式 1.1.宏介绍 1.2.原理详解 1.3.宏的可变参数 1.4.案例分析 1.5.其他实例 2.C之std::initializer_list 2.1.简介 2.2.原理详解 2.3.案例分析 3.C之可变参数模版 3.1.简介 3.2.可变参数个数 3.3.递归包展开 3.4.逗号表达式展开 3.5…...
Centos7.9和Debian12部署Minio详细流程
一、安装minio Centos wget https://dl.min.io/server/minio/release/linux-amd64/archive/minio-20230227181045.0.0.x86_64.rpm -O minio.rpm sudo dnf install minio.rpmDebian wget https://dl.min.io/server/minio/release/linux-amd64/archive/minio_20230227181045.0…...
软件测试|教你如何使用UPDATE修改数据
简介 在SQL(Structured Query Language)中,UPDATE语句用于修改数据库表中的数据。通过UPDATE语句,我们可以更新表中的特定记录或多条记录,从而实现数据的修改和更新。本文将详细介绍SQL UPDATE语句的语法、用法以及一…...
新闻稿发布:媒体重要还是价格重要
在当今信息爆炸的数字时代,企业推广与品牌塑造不可或缺的一环就是新闻稿发布。新闻稿是一种通过媒体渠道传递企业信息、宣传品牌、事件或产品新闻的文本形式。发布新闻稿的过程旨在将企业的声音传递给更广泛的受众,借助媒体平台实现品牌故事的广泛传播。…...
prometheus grafana mysql监控配置使用
文章目录 前传bitnami/mysqld-exporter:0.15.1镜像出现了问题.my.cnf可以用这个"prom/mysqld-exporter:v0.15.0"镜像重要的事情mysql监控效果外传 前传 prometheus grafana的安装使用:https://nanxiang.blog.csdn.net/article/details/135384541 本文说…...
鸿蒙HarmonyOS-带笔锋手写板(三)
笔者用ArkTS 写了一个简单的带笔锋的手写板应用,并且可以将手写内容保存为图片。 一、效果图 手写效果如下(在鸿蒙手机模拟器上运行,手写时反应可能会有点慢) 二、实现方法 参考文章: 支持笔锋效果的手写签字控件_a…...
React 实现 Step组件
简介 本文将会实现步骤条组件功能。步骤条在以下几个方面改进。 1、将url与Step组件绑定,做到浏览器刷新,不会重定向到Step 1 2、通过LocalStorage 存储之前的Step,做到不丢失数据。 实现 Step.jsx (组件) import {useEffect, useState} fro…...
【OJ】单链表刷题
力扣刷题 1. 反转链表(206)1.1 题目描述1.2 题目分析1.2.1 头插法1.2.2 箭头反转 1.3 题目代码1.3.1 头插入1.3.2 箭头反转 2.合并两个有序链表(21)2.1 题目描述2.2 题目分析2.3 题目代码 1. 反转链表(206)…...
【UML建模】部署图(Deployment Diagram)
1.概述 部署图是一种结构图,用于描述软件系统在不同计算机硬件或设备上的部署和配置情况,以图形化的方式展示系统中组件、节点和连接之间的物理部署关系。 通过部署图,可以清晰地了解系统的物理结构和部署方式,包括系统组件和节…...
三、计算机理论-关系数据库-数据模型与数据视图;关系代数、关系演算及关系模型
数据模型 具体事物-抽象化-->概念模型-数据化-->数据模型 概念模型也称信息模型,在数据库设计阶段,由设计者按照用户的观点对数据和信息建模,实现对现实世界的概念抽象; 数据模型主要包括网状模型、层次模型、关系模型、面向…...
解读 $mash 通证 “Fair Launch” 规则(Staking 玩法解读篇)
Solmash 是 Solana 生态中由社区主导的铭文资产 LaunchPad 平台,该平台旨在为 Solana 原生铭文项目,以及通过其合作伙伴 SoBit 跨链桥桥接到 Solana 的 Bitcoin 生态铭文项目提供更广泛的启动机会。...
【C语言】关于C11的一些新特性
相比于VC 6.0使用的ANSI C标准,VS2022使用的C11标准与上一代有很多不同,相比之前的 C 标准(如 C89/C90 和 C99),引入了一些新的功能、特性和改进。以下是 C11 标准相对于之前版本的一些主要变化和新增内容:…...
牛的速记(c++题解)
题目描述 奶牛们误解了速记的含义。他们是这样理解的: 给出一个少于255个字母的小写字母串。 找到一个出现次数最多的字母,将该字母从字母串中统统删去,如果出现次数最多的字母不止一个,就删去在字母表中靠前的一个,即…...
使用ffmpeg+flv.js + websokect播放rtsp格式视频流
对于rtsp的视频流网上有很多种的解决方案,但是大的趋势还是利用ffmpeg的工具进行rtsp的视频解析进行一个推流,我最终选择bilibili开源的flv.js,代码十分的简单全部都在底层封装好了。实现的方式也比较容易理解,ffmpeg进行rtsp的视…...
OAI openair3代码结构整理
openair3代码框架结构 OAI(OpenAirInterface)是一个开源的5G网络软件平台,用于研究和开发5G网络技术。OpenAir3是OAI项目中的一个子项目,专注于5G核心网络的功能实现。 一、OpenAir3的代码主要包括以下几个部分: NAS…...
Kubernets(K8S)启动和运行 01-01 Kubernetes简介
Kubernets(K8S)启动和运行 01-01 Kubernetes简介 Kubernetes is an open source orchestrator for deploying containerized applications. It was originally developed by Google, inspired by a decade of experience deploying scalable, reliable systems in containers …...
烟台制作网站有哪些/昆明网站seo公司
今天早上刘sir给我们教怎么样创建自己的博客,第一次接触这个东西,觉得很有趣,很不错,希望以后再这里能学习到跟多的知识,认识更多的朋友. QQ:403378100转载于:https://blog.51cto.com/3088278/563525...
网站企业优化/中国国家数据统计网
专注于机械行业、专业、职业信息分享服务于制造业百万工程师推荐阅读【机械制图】画图这么久,线型都没搞懂?【机械制图】机械图纸知识解析,这个总结溜溜的【机械制图】机械图纸尺寸标注规则,通过动图复习一下!知名机械…...
拉丝机东莞网站建设/日本搜索引擎naver入口
Win 7英文系统显示中文乱码的解决http://www.enet.com.cn/article/2011/0811/A20110811896633.shtml 请点击Startmenu并点击Control Panel来打开控制面板,点击Clock Language andRegion下面的Change display language, 在弹出窗口中点击Administrative选项卡, 将Cur…...
中国互联网协会网站/能让手机流畅到爆的软件
在实际工作中经常遇到以下问题:邮件发送给错误的收件人,简而言之就是邮件发错了,如果遇到群发更麻烦。Exchange中提供了批量删除邮件功能,当用户发现发送错误后,管理员可以检索并删除指定的邮件。 案例任务:…...
网站建设制作网站/企业培训视频
点击上方蓝色字体,选择“标星公众号”优质文章,第一时间送达关注公众号后台回复pay或mall获取实战项目资料视频作者:我是小茗同学来源:https://www.cnblogs.com/liuxianan1. 前言个人网站最近增加了评论功能,为了方便用…...
wordpress不能将请求写入临时文件./免费推广广告链接
第二十九讲 抽象类 抽象类:专门用于继承的类1.声明一个抽象类使用abstract关键字2.一个抽象类中可以包含几个抽象方法。也使用abstract3.抽象类中可以存在非抽象的方法4.抽象类不能被直接被实例化 覆盖父类中的抽象方法 override 代码部分 private void Form1_Load(…...