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

思路

一串数字排列的下一个排序找法是:从末尾开始找第一次出现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;}}}
}

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/85113.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Jenkins 中 shell 脚本执行失败却不自行退出

Jenkins 中 执行 shell 脚本时&#xff0c;有时候 shell 执行失败了&#xff0c;或者判断结果是错误的&#xff0c;但是 Jenkins 执行完成后确提示成功 success 。 此时&#xff0c;可以通过条件判断来解决这个问题&#xff0c;让 Jenkins 强制退出并提示执行失败 failed 。 …

Nginx使用proxy_cache指令设置反向代理缓存静态资源

场景 CentOS7中解压tar包的方式安装Nginx&#xff1a; CentOS7中解压tar包的方式安装Nginx_centos7 tar文件 怎么load_霸道流氓气质的博客-CSDN博客 参考上面流程实现搭建Nginx的基础上&#xff0c;实现静态资源的缓存设置。 注意上面安装时的目录是在/opt/nginx目录下&…

win10 + VS2022 安装opencv C++

最近需要用到C opencv&#xff0c;看了很多帖子都需要自己编译opencv源码。为避免源码编译&#xff0c;可以使用VS来配置opencv C。下面是主要过程&#xff1a; 目录 1. 从官网下载 opencv - Get Started - OpenCV 2. 点击这个exe文件进行安装 3. 配置环境变量 4. VS中的项…

java spring cloud 企业电子招标采购系统源码:营造全面规范安全的电子招投标环境,促进招投标市场健康可持续发展 tbms

​ 项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以…

Word转PDF工具哪家安全?推荐好用的文件格式转换工具

Word文档是我们最常见也是最常用的办公软件&#xff0c;想必大家都知道了Word操作起来十分的简单&#xff0c;而且功能也是比较齐全的。随着科技的不断进步&#xff0c;如今也是有越来越多类型的办公文档&#xff0c;PDF就是其中之一&#xff0c;那么word转pdf怎么转?Word转PD…

DSP学习笔记

TI公司提供的c/c编译器&#xff0c;可以将其变成dsp语言。char类型本来是8位&#xff0c;在dsp里面是16位&#xff0c;int也是16位&#xff0c;long才是32位&#xff0c;float也是32位&#xff0c;enum是16位&#xff0c;double32位&#xff0c;long double是32位&#xff0c;p…

客户端脚本安全

客户端脚本安全 白帽子讲web安全 ———— a.了解web安全测试的基本知识 b.掌握前端的脚本安全知识&#xff0c;了解基本的前端安全测试条目&#xff0c;如同源策略、xss攻击测试、CSRF测试、点击劫持测试 c.webinsepct nessus 绿盟扫描 数据流 输入输出 浏览器安全 同源…

【HCIP】重发布实验

题目&#xff1a; 配置&#xff1a; R1 //配置ip地址 [r1]int g0/0/0 [r1-GigabitEthernet0/0/0]ip add 12.1.1.1 24 [r1-GigabitEthernet0/0/0]int g0/0/1 [r1-GigabitEthernet0/0/1]ip add 13.1.1.1 24 [r1-GigabitEthernet0/0/1]int lo0 [r1-LoopBack0]ip add 1.1.1.1 24 /…

MySQL—日志

这里写目录标题 undo logundo log的作用undo log页记录的是什么 Buffer Pool为什么需要Buffer PoolBuffer Pool缓存什么 redo log什么是redo logredo log的作用redo log什么时候刷盘undo和redo的区别 binlogbinlog 作用redo log和binlog区别如果数据数据被删了&#xff0c;能用…

【redis】redis的认识和安装

目录 1.redis是什么2.Redis的特点3.安装redis4.设置远程连接4.1 开启隧道4.2 可视化客户端连接4.3 开启防火墙 5.redis常见数据类型5.1 redis的一些全局命令5.2 数据结构 6. redis的典型应用---缓存&#xff08;cache&#xff09;6.1 使用redis做缓存6.2 缓存穿透&#xff0c;缓…

并发——Atomic 原子类总结

文章目录 1 Atomic 原子类介绍2 基本类型原子类2.1 基本类型原子类介绍2.2 AtomicInteger 常见方法使用2.3 基本数据类型原子类的优势2.4 AtomicInteger 线程安全原理简单分析 3 数组类型原子类3.1 数组类型原子类介绍3.2 AtomicIntegerArray 常见方法使用 4 引用类型原子类4.1…

wordpress数据表中标签和分类如何区分?

wordpress中标签和分类是什么关系怎么区分&#xff1f;最后有一个群的网友告诉了我文章ID和标签ID的关系是放在了wp_term_relationships表中&#xff0c;然后我百度了下这个表的结构和相关介绍&#xff0c;发现果然如此&#xff0c;先把文章保存起来&#xff1a; wp_term_rela…

EasyPoi导出 导入(带校验)简单示例 EasyExcel

官方文档 : http://doc.wupaas.com/docs/easypoi pom的引入: <!-- easyPoi--><dependency><groupId>cn.afterturn</groupId><artifactId>easypoi-spring-boot-starter</artifactId><version>4.0.0</version></dep…

Java培训班出来能找到工作吗?有没有想详细了解的呢

参加Java培训班可以提升你的编程技能和就业竞争力&#xff0c;但能否找到工作还取决于多个因素&#xff0c;如个人能力、市场需求、就业竞争等。参加Java培训班可以帮助你获得系统的Java编程知识和实践经验&#xff0c;了解行业最佳实践和流行的技术框架。这有助于你在面试时展…

谷粒商城第十天-分组新增级联显示商品分类分组修改级联回显商品分类

目录 一、总述 二、前端实现 三、后端实现 四、总结 一、总述 本次就是一个小的优化。 就是分组新增或者是修改的时候&#xff0c;直接显示商品分类的id可读性不高&#xff0c;新增的时候需要填写对商品分类的id&#xff0c;修改的时候&#xff0c;就只是给你一个商品分类…

CelebA-HQ数据集下载【详细明了版】分辨率包括【64,128,256,512,1024】

CelebA-HQ数据集下载&#xff0c;分辨率包括【64&#xff0c;128&#xff0c;256&#xff0c;512&#xff0c;1024】 前言下载&处理1.下载合并解压img_celeba.7z2.下载list_landmarks_celeba.txt3.获取h5tool.py4.mkdir5. 下载.dat数据 配置环境生成数据集 前言 CelebA-HQ …

vue插槽slots

一、默认插槽&#xff1a; vue组件能够接收任意类型的 JavaScript 值作为 props&#xff0c;也可以为子组件传递一些模板片段&#xff0c;让子组件在它们的组件中渲染这些片段。 例如&#xff1a;有一个<FancyButton>组件 在父组件中引用 最终渲染出来的dom 插槽内容可…

配置中心替换测试设计分享

一、背景 项目后端服务开始一直使用Apollo配置中心(携程开发)进行配置管理&#xff0c;由于公司自研了配置中心B&#xff0c;为了后续方便管理和降本增效&#xff0c;后端服务使用的配置需要由Apollo配置中心切换到自研配置中心B。后续不再使用Apollo配置。 替换前架构&#x…

刷新缓冲区(标准IO)

标准IO是带缓冲的&#xff0c;输入和输出函数属于行缓冲&#xff0c;stdin、stdin、printf、scanf 1.换行符刷新 2.缓冲区满刷新 3.fflush函数强制刷新 4.程序正常结束

【云原生】K8S集群

目录 一、调度约束1.1 POT的创建过程1.1调度过程 二、指定节点调度2.1 通过标签选择节点 三、亲和性3.1requiredDuringSchedulingIgnoredDuringExecution&#xff1a;硬策略3.1 preferredDuringSchedulingIgnoredDuringExecution&#xff1a;软策略3.3Pod亲和性与反亲和性3.4使…