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 <= 1000 <= nums[i] <= 100
思路
一串数字排列的下一个排序找法是:从末尾开始找第一次出现nums[ i ] >nums[ i-1 ] 的位置,在 i -1之前的数字排序不变,在 i -1之后寻找大于nums[ i-1 ]的最小值,找到后与nums[ i-1 ]交换。交换后,i - 1之后的数字按非递减排序即可。

代码
#include<stdio.h>
#include<stdlib.h>void nextPermutation(int* nums, int numsSize);int main()
{int nums[3]={1};int size=1;nextPermutation(nums,size);for(int i=0;i<size;i++){printf("%d ",nums[i]);}return 0;
}void nextPermutation(int* nums, int numsSize)
{int sign=0;int i;for(i=numsSize-1;i>0&&nums[i]<=nums[i-1];i--);if(numsSize==1)return ;if(i==0&&nums[i+1]<=nums[i]){int left=0,right=numsSize-1;while(left<right){int x=nums[left];nums[left]=nums[right];nums[right]=x;left++;right--;}}else{int target=i;int min=nums[i];for(int j=i+1;j<numsSize;j++){if(nums[j]>nums[i-1]&&nums[j]<min){min=nums[j];target=j;}}int a=nums[target];nums[target]=nums[i-1];nums[i-1]=a;int len=numsSize-i;for(int p=len/2;p>=1;p=p/2){for(int q=i+p;q<numsSize;q++){int temp=nums[q];int j;for(j=q-p;j>=i&&nums[j]>temp;j=j-p){nums[j+p]=nums[j];}nums[j]=temp;}}}
}
相关文章:
LeetCode 31题:下一个排列
目录 题目 思路 代码 题目 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如,arr [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序…...
CMake:检测python模块和包
CMake:检测python模块和包 导言项目结构CMakeLists.txt相关源码 导言 上一篇,我们基本了解了如何去检测python的解释器和python库。通常,代码是依赖于特定的python模块,无论是python工具、嵌入python的程序,还是扩展python的库。…...
02Mysql之多表查询--例题讲解
一、题目详情,以及表的建立 新增员工表emp和部门表deptcreate table dept (dept1 int ,dept_name varchar(11));create table emp (sid int ,name varchar(11),age int,worktime_start date,incoming int,dept2 int);insert into dept values(101,财务),(102,销售)…...
虹科方案 | 汽车总线协议转换解决方案
汽车总线: 汽车总线是一种用于在车辆电子系统中传输数据和控制信息的通信系统。它允许不同的电子控制单元(ECU)在车辆中相互通信,协调各个系统的操作,以实现功能的集成和协同工作。 在现代汽车中,综合通信…...
Mr. Cappuccino的第59杯咖啡——简单手写SpringIOC框架
简单手写SpringIOC框架 环境搭建基于XML方式项目结构项目代码运行结果 基于注解方式项目结构项目代码运行结果 简单手写SpringIOC框架核心原理基于XML方式原理项目结构项目代码运行结果 基于注解方式原理项目结构项目代码运行结果 环境搭建 基于XML方式 项目结构 项目代码 p…...
爬虫 学习HTML标签和元素的基本概念,了解网页的结构和内容
HTML(Hypertext Markup Language)是一种用于创建网页的标记语言,由一系列的标签组成。标签使用尖括号(< 和 >)包围,并且通常成对出现,一个是开始标签,一个是结束标签。 HTML文…...
mysql将id重新修改为递增
文章目录 场景解决,排序的话可以先按照一定大小改一下,然后将id字段删掉,再重新生成即可清空表数据,并将自增id改为1开始 场景 好比我有个配置表: CREATE TABLE config (id int NOT NULL AUTO_INCREMENT,config_key varchar(20) NOT NULL,config_value varchar(500) NOT NU…...
http、https笔记
目录 HTTP 基本概念状态码:get和post的区别:http 常⻅字段:http的缺点: HTTP/1.1HTTP/3HTTPSHTTPS和HTTP区别对称加密和⾮对称加密⾮对称加密 HTTP 基本概念 状态码: 1xx 中间状态,比如post的continue 20…...
飞凌嵌入式「国产」嵌入式核心板大盘点(三)——龙芯中科、赛昉科技
为了帮助各位工程师朋友详细了解飞凌嵌入式推出的“国产化”产品,小编专门开设了「国产平台大盘点专题」。上周,已经带大家盘点了飞凌嵌入式联合瑞芯微电子和全志科技两个国产处理器品牌打造的平台,今天,将继续为大家介绍龙芯和赛…...
以vue2为例,用npm开发环境在后端部署vue2项目(更推荐使用nginx部署)
因为之前一致出现的跨域问题,从而想到了这个办法,属于偏方。推荐使用nginx部署,再去解决跨域问题。 接下来聊一聊本文所使用的方法。 首先将你的前端vue项目拷贝一份到服务器,准备一个dockerfile文件,用这个进行部署首…...
docker容器监控:Cadvisor +Prometheus+Grafana的安装部署
目录 Cadvisor PrometheusGrafana的安装部署 一、安装docker: 1、安装docker-ce 2、阿里云镜像加速器 3、下载组件镜像 4、创建自定义网络 二、部署Cadvisor 1、被监控主机上部署Cadvisor容器 2、访问cAdvisor页面 三、安装prometheus 1、部署Prometheus…...
前端食堂技术周刊第 93 期:7 月登陆 Web 平台的新功能、Node.js 工具箱、Nuxt3 开发技巧、MF 重构方案
美味值:🌟🌟🌟🌟🌟 口味:橙橙冰萃美式 食堂技术周刊仓库地址:https://github.com/Geekhyt/weekly 大家好,我是童欧巴。欢迎来到前端食堂技术周刊,我们先来…...
获取 Android 的 SHA1 值
1、调试版,可以直接在 Android studio 中的 gradle 中查看。也可以用下面方法进行 前提要先确定签名文件所在的路径:调试版默认使用的签名文件是debug.keystore,文件处于 C 盘用户目录下的.android文件夹下。打开命令行工具, 1、…...
! [remote rejected] develop -> develop (pre-receive hook declined)
问题 git push 远程提交dao develop 分支失败,出现下面错误信息 remote: GitLab: You are not allowed to push code to protected branches on this project. To https://xxx.com.cn/xxx/xxx/xxx/xxx.git/! [remote rejected] develop -> develop (pre-receiv…...
最强的表格组件—AG Grid使用以及License Key Crack
PS: 想要官方 License Key翻到最后面 Ag Grid简介 Ag-Grid 是一个高级数据网格,适用于JavaScript/TypeScript应用程序,可以使用React、Angular和Vue等流行框架进行集成。它是一种功能强大、灵活且具有高度可定制性的表格解决方案,提供了丰富…...
【算法】逆波兰表达式
文章目录 定义求法代码思想: 定义 逆波兰表达式也称为“后缀表达式”,是将运算符写在操作数之后的运算式。 求法 *如:(ab)c-(ab)/e的转换过程: 先加上所有的括号。 (((ab)*c)-((ab)/e))将所有的运算符移到括号外面 (((ab) c)* …...
添加SQLCipher 到项目中
文章目录 一、克隆下载SQLCipher二、手动导入1. 生成sqlite3.c2. 在项目中添加命令3. 添加 Security.framework 三、CocoaPods导入 SQLCipher官方地址 一、克隆下载SQLCipher $ cd ~/Documents/code $ git clone https://github.com/sqlcipher/sqlcipher.git二、手动导入 1.…...
轻松预约,尽享美食,详解餐厅预约小程序的设计与实现
随着智能手机的普及和人们生活水平的提高,餐厅预约已经成为人们日常生活中的一部分。为了更好地满足人们的需求,许多餐厅开始使用小程序来提供更方便快捷的预约服务。本文将介绍如何制作一款餐厅预约小程序的详细步骤。 1. 进入乔拓云网后台,…...
数据结构--栈和队列3.1(栈-顺序结构)
目录 栈(Stack)栈顶(top)栈底(bottom)空栈(不含任何元素) 创建栈 入栈操作 出栈操作 销毁一个栈 计算栈的当前容量 实例分析 栈的插入操作叫做进栈(Push…...
pdf怎么压缩到1m?这样做压缩率高!
PDF是目前使用率比较高的一种文档格式,因为它具有很高的安全性,还易于传输等,但有时候当文件体积过大时,会给我们带来不便,这时候简单的解决方法就是将其压缩变小。 想要将PDF文件压缩到1M,也要根据具体的情…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...
软件工程 期末复习
瀑布模型:计划 螺旋模型:风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合:模块内部功能紧密 模块之间依赖程度小 高内聚:指的是一个模块内部的功能应该紧密相关。换句话说,一个模块应当只实现单一的功能…...
深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学
一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件,其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时,价带电子受激发跃迁至导带,形成电子-空穴对,导致材料电导率显著提升。…...
用鸿蒙HarmonyOS5实现国际象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的国际象棋小游戏的完整实现代码,使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├── …...
