当前位置: 首页 > news >正文

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;}}}
}

 

 

相关文章:

LeetCode 31题:下一个排列

目录 题目 思路 代码 题目 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序…...

CMake:检测python模块和包

CMake:检测python模块和包 导言项目结构CMakeLists.txt相关源码 导言 上一篇&#xff0c;我们基本了解了如何去检测python的解释器和python库。通常&#xff0c;代码是依赖于特定的python模块&#xff0c;无论是python工具、嵌入python的程序&#xff0c;还是扩展python的库。…...

02Mysql之多表查询--例题讲解

一、题目详情&#xff0c;以及表的建立 新增员工表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,销售)…...

虹科方案 | 汽车总线协议转换解决方案

汽车总线&#xff1a; 汽车总线是一种用于在车辆电子系统中传输数据和控制信息的通信系统。它允许不同的电子控制单元&#xff08;ECU&#xff09;在车辆中相互通信&#xff0c;协调各个系统的操作&#xff0c;以实现功能的集成和协同工作。 在现代汽车中&#xff0c;综合通信…...

Mr. Cappuccino的第59杯咖啡——简单手写SpringIOC框架

简单手写SpringIOC框架 环境搭建基于XML方式项目结构项目代码运行结果 基于注解方式项目结构项目代码运行结果 简单手写SpringIOC框架核心原理基于XML方式原理项目结构项目代码运行结果 基于注解方式原理项目结构项目代码运行结果 环境搭建 基于XML方式 项目结构 项目代码 p…...

爬虫 学习HTML标签和元素的基本概念,了解网页的结构和内容

HTML&#xff08;Hypertext Markup Language&#xff09;是一种用于创建网页的标记语言&#xff0c;由一系列的标签组成。标签使用尖括号&#xff08;< 和 >&#xff09;包围&#xff0c;并且通常成对出现&#xff0c;一个是开始标签&#xff0c;一个是结束标签。 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 基本概念状态码&#xff1a;get和post的区别&#xff1a;http 常⻅字段&#xff1a;http的缺点&#xff1a; HTTP/1.1HTTP/3HTTPSHTTPS和HTTP区别对称加密和⾮对称加密⾮对称加密 HTTP 基本概念 状态码&#xff1a; 1xx 中间状态&#xff0c;比如post的continue 20…...

飞凌嵌入式「国产」嵌入式核心板大盘点(三)——龙芯中科、赛昉科技

为了帮助各位工程师朋友详细了解飞凌嵌入式推出的“国产化”产品&#xff0c;小编专门开设了「国产平台大盘点专题」。上周&#xff0c;已经带大家盘点了飞凌嵌入式联合瑞芯微电子和全志科技两个国产处理器品牌打造的平台&#xff0c;今天&#xff0c;将继续为大家介绍龙芯和赛…...

以vue2为例,用npm开发环境在后端部署vue2项目(更推荐使用nginx部署)

因为之前一致出现的跨域问题&#xff0c;从而想到了这个办法&#xff0c;属于偏方。推荐使用nginx部署&#xff0c;再去解决跨域问题。 接下来聊一聊本文所使用的方法。 首先将你的前端vue项目拷贝一份到服务器&#xff0c;准备一个dockerfile文件&#xff0c;用这个进行部署首…...

docker容器监控:Cadvisor +Prometheus+Grafana的安装部署

目录 Cadvisor PrometheusGrafana的安装部署 一、安装docker&#xff1a; 1、安装docker-ce 2、阿里云镜像加速器 3、下载组件镜像 4、创建自定义网络 二、部署Cadvisor 1、被监控主机上部署Cadvisor容器 2、访问cAdvisor页面 三、安装prometheus 1、部署Prometheus…...

前端食堂技术周刊第 93 期:7 月登陆 Web 平台的新功能、Node.js 工具箱、Nuxt3 开发技巧、MF 重构方案

美味值&#xff1a;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f; 口味&#xff1a;橙橙冰萃美式 食堂技术周刊仓库地址&#xff1a;https://github.com/Geekhyt/weekly 大家好&#xff0c;我是童欧巴。欢迎来到前端食堂技术周刊&#xff0c;我们先来…...

获取 Android 的 SHA1 值

1、调试版&#xff0c;可以直接在 Android studio 中的 gradle 中查看。也可以用下面方法进行 前提要先确定签名文件所在的路径&#xff1a;调试版默认使用的签名文件是debug.keystore&#xff0c;文件处于 C 盘用户目录下的.android文件夹下。打开命令行工具&#xff0c; 1、…...

! [remote rejected] develop -> develop (pre-receive hook declined)

问题 git push 远程提交dao develop 分支失败&#xff0c;出现下面错误信息 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 是一个高级数据网格&#xff0c;适用于JavaScript/TypeScript应用程序&#xff0c;可以使用React、Angular和Vue等流行框架进行集成。它是一种功能强大、灵活且具有高度可定制性的表格解决方案&#xff0c;提供了丰富…...

【算法】逆波兰表达式

文章目录 定义求法代码思想&#xff1a; 定义 逆波兰表达式也称为“后缀表达式”&#xff0c;是将运算符写在操作数之后的运算式。 求法 *如&#xff1a;(ab)c-(ab)/e的转换过程&#xff1a; 先加上所有的括号。 (((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.…...

轻松预约,尽享美食,详解餐厅预约小程序的设计与实现

随着智能手机的普及和人们生活水平的提高&#xff0c;餐厅预约已经成为人们日常生活中的一部分。为了更好地满足人们的需求&#xff0c;许多餐厅开始使用小程序来提供更方便快捷的预约服务。本文将介绍如何制作一款餐厅预约小程序的详细步骤。 1. 进入乔拓云网后台&#xff0c;…...

数据结构--栈和队列3.1(栈-顺序结构)

目录 栈&#xff08;Stack&#xff09;栈顶&#xff08;top&#xff09;栈底&#xff08;bottom&#xff09;空栈&#xff08;不含任何元素&#xff09; 创建栈 入栈操作 出栈操作 销毁一个栈 计算栈的当前容量 实例分析 栈的插入操作叫做进栈&#xff08;Push&#xf…...

pdf怎么压缩到1m?这样做压缩率高!

PDF是目前使用率比较高的一种文档格式&#xff0c;因为它具有很高的安全性&#xff0c;还易于传输等&#xff0c;但有时候当文件体积过大时&#xff0c;会给我们带来不便&#xff0c;这时候简单的解决方法就是将其压缩变小。 想要将PDF文件压缩到1M&#xff0c;也要根据具体的情…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

论文阅读:Matting by Generation

今天介绍一篇关于 matting 抠图的文章&#xff0c;抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法&#xff0c;已经有很多的工作和这个任务相关。这两年 diffusion 模型很火&#xff0c;大家又开始用 diffusion 模型做各种 CV 任务了&am…...

【PX4飞控】mavros gps相关话题分析,经纬度海拔获取方法,卫星数锁定状态获取方法

使用 ROS1-Noetic 和 mavros v1.20.1&#xff0c; 携带经纬度海拔的话题主要有三个&#xff1a; /mavros/global_position/raw/fix/mavros/gpsstatus/gps1/raw/mavros/global_position/global 查看 mavros 源码&#xff0c;来分析他们的发布过程。发现前两个话题都对应了同一…...

【大厂机试题解法笔记】矩阵匹配

题目 从一个 N * M&#xff08;N ≤ M&#xff09;的矩阵中选出 N 个数&#xff0c;任意两个数字不能在同一行或同一列&#xff0c;求选出来的 N 个数中第 K 大的数字的最小值是多少。 输入描述 输入矩阵要求&#xff1a;1 ≤ K ≤ N ≤ M ≤ 150 输入格式 N M K N*M矩阵 输…...