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

LeetCode刷题之31.下一个排列

文章目录

  • 1. 题目
  • 2.分析
  • 3.解答
    • 3.1 先排序,后交换
    • 3.2 先交换,后排序

1. 题目

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如,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 的下一个排列。

必须 原地 修改,只允许使用额外常数空间。

2.分析

这里需要找下一个字典序更大的排列,那么意味着要从数组的后端入手。如果最后两个元素原本就是升序的,那么就直接交换这两个元素就好了,这个组合即使下一个更大的组合。在这里插入图片描述
但是,如果这两个元素不是升序的,那么交换这两个元素反而导致拍列更小。因此,必须要找到从后向前数的第一个升序排列的两个相邻元素。找到之后,交换这两个元素即可。
请添加图片描述
但是,交换后的元素依然不一定是下一个更大排列组合。如[5,7,6,4]这个排列,交换5和7,得到的是[7,5,6,4]这个组合,显然不是下一个更大排列,毕竟手动排列组合一下,发现下一个组合应该是[6,4,5,7]
请添加图片描述

那么,应该是考虑从后向前第一个升序段的后一个元素开始,将后面所有的元素按字典排序,然后找到紧挨着升序点前一个元素的那个元素,将其交换即可。
或者找到紧挨着升序段前一个元素的数据,将其进行交换,然后将从升序段后一个元素开始的数据,按字典方式排序。

3.解答

3.1 先排序,后交换

public class Solution {public void nextPermutation(int[] nums) {if (nums.length <= 1) return;int len = nums.length;for (int i = len - 1; i > 0;i--) {if (nums[i] > nums[i - 1]) {Arrays.sort(nums, i, len);for (int j = i; j < len; j++) {if (nums[j] > nums[i - 1]) {int temp = nums[j];nums[j] = nums[i - 1];nums[i - 1] = temp;return;}}}}Arrays.sort(nums);}
}

3.2 先交换,后排序

public class Soultion {public void nextPermutation(int[] nums) {if (nums.length <= 1) return;int i = nums.length - 2;int j = nums.length - 1;int k = nums.length - 1;while (i >= 0 && nums[i] >= nums[j]) {i--;j--;} if (i >= 0) {while (nums[i] > num[k]) {k--;}swap(nums, i, k);}Arrays.sort(nums, j, nums.length);}private void swap(int[], int i, int k) {int temp = nums[i];nums[i] = nums[k];nums[k] = temp;}
}

相关文章:

LeetCode刷题之31.下一个排列

文章目录 1. 题目2.分析3.解答3.1 先排序&#xff0c;后交换3.2 先交换&#xff0c;后排序 1. 题目 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3…...

【RISC-V 指令集】RISC-V 向量V扩展指令集介绍(九)- 向量定点算术指令

1. 引言 以下是《riscv-v-spec-1.0.pdf》文档的关键内容&#xff1a; 这是一份关于向量扩展的详细技术文档&#xff0c;内容覆盖了向量指令集的多个关键方面&#xff0c;如向量寄存器状态映射、向量指令格式、向量加载和存储操作、向量内存对齐约束、向量内存一致性模型、向量…...

【Java网络编程】IP网络协议与TCP、UDP网络传输层协议

1.1、IP协议 当应用层的数据被封装后&#xff0c;想要将数据在网络上传输&#xff0c;数据究竟要被发往何处&#xff0c;又该如何精准的在网络上定位目标机器&#xff0c;此时起到关键作用的就是“IP协议”。IP协议的作用在于把各种数据包准确无误的传递给目标方&#xff0c;其…...

C# 分布式自增ID算法snowflake(雪花算法)

文章目录 1. 概述2. 结构3. 代码3.1 IdWorker.cs3.2 IdWorkerTest.cs (测试) 1. 概述 分布式系统中&#xff0c;有一些需要使用全局唯一ID的场景&#xff0c;这种时候为了防止ID冲突可以使用36位的UUID&#xff0c;但是UUID有一些缺点&#xff0c;首先他相对比较长&#xff0c…...

commonJS和esModule的应用

commonJS commonJS规范的核心变量是&#xff1a;exports&#xff0c;module.exports&#xff0c;require exports 和 module.exports可以负责模块的导出require 负责模块的导入 module.exports 导出方案&#xff1a; const name yx const age 18// 1 导出方案 module.exp…...

(十一)RabbitMQ及SpringAMQP

1.初识MQ 1.1.同步和异步通讯 微服务间通讯有同步和异步两种方式&#xff1a; 同步通讯&#xff1a;就像打电话&#xff0c;需要实时响应。 异步通讯&#xff1a;就像发邮件&#xff0c;不需要马上回复。 两种方式各有优劣&#xff0c;打电话可以立即得到响应&#xff0c;…...

STM32 M3内核寄存器概念

内容主要来自<<M3内核权威指南>> 汇编程序中的最低有效位&#xff08;Least Significant Bit&#xff09;。LSB是二进制数中最右边的位&#xff0c;它代表了数值中的最小单位。在汇编程序中&#xff0c;LSB通常用于表示数据的最小精度或者作为标志位。 ---------…...

SQL语句的编写

##创建用户-建表建库 #创建一个用户名为 feng&#xff0c;允许从任何主机 % 连接&#xff0c;并使用密码 sc123456 进行身份验证的用户。 rootTENNIS 16:33 scmysql>create user feng% identified by sc123456; Query OK, 0 rows affected (0.04 sec) #创建一个名为fen…...

Lecture 1~3 About Filter

文章目录 空间域上的滤波器- 线性滤波器盒状滤波器Box Filter锐化Sharpening相关运算 vs. 卷积运算 Correlation vs. Convolution - 非线性滤波器高斯滤波器Gaussian filter - 实际问题- 纹理texture 频域上的滤波器 滤波的应用- 模板匹配- 图像金字塔 空间域上的滤波器 图像…...

配置vscode链接linux

1.安装 remote SSH 2.按F1 ssh ljh服务器公网ip 3. 选择保存远端host到本地 某位置 等待片刻后 4. 切换到远程资源管理器中 应该可以看到一台电脑&#xff0c;右键在当前窗口链接&#xff0c;输入你的服务器用户密码后电脑变绿说明远程连接成功 5.一定要登陆上云服务器后再…...

论文阅读——MVDiffusion

MVDiffusion: Enabling Holistic Multi-view Image Generation with Correspondence-Aware Diffusion 文生图模型 用于根据给定像素到像素对应关系的文本提示生成一致的多视图图像。 MVDiffusion 会在给定任意每个视图文本的情况下合成高分辨率真实感全景图像&#xff0c;或将…...

Linux中的网络命令深度解析与CentOS实践

Linux中的网络命令深度解析与CentOS实践 在Linux系统中,网络命令是管理和诊断网络问题的关键工具。无论是网络管理员还是系统开发者,熟练掌握这些命令都是必不可少的。本文将深入探讨Linux中常用的网络命令,并以CentOS为例,展示这些命令的具体应用。 一、ping命令 ping命…...

nginx配置实例(反向代理)

目录 一、目标-反向代理实现效果 二、安装tomcat 三、配置nginx服务 四、配置反向代理 一、目标-反向代理实现效果 访问过程分析&#xff1a; 二、安装tomcat 1、安装jdk环境 新建/export/server目录 解压jdk 查看是否解压成功 配置jdk软连接 进入jdk的bin目录中&#x…...

Flutter 解决NestedScrollView与TabBar双列表滚动位置同步问题

文章目录 前言一、需要实现的效果如下二、flutter实现代码如下&#xff1a;总结 前言 最近写flutter项目&#xff0c;遇到NestedScrollView与TabBar双列表滚动位置同步问题&#xff0c;下面是解决方案&#xff0c;希望帮助到大家。 一、需要实现的效果如下 1、UI图&#xff1…...

云计算存在的安全隐患

目录 一、概述 二、ENISA云安全漏洞分析 三、云计算相关系统漏洞 3.1 概述 3.2 漏洞分析 3.2.1 Hypervisor漏洞 3.2.1.1 CVE-2018-16882 3.2.1.2 CVE-2017-17563 3.2.1.3 CVE-2010-1225 3.2.2 虚拟机漏洞 3.2.2.1 CVE-2019-14835 3.2.2.2 CVE-2019-5514 3.2.2.3 CV…...

黑翅鸢优化算法(BKA)-2024年SCI一区新算法-公式原理详解与性能测评 Matlab代码免费获取

声明&#xff1a;文章是从本人公众号中复制而来&#xff0c;因此&#xff0c;想最新最快了解各类智能优化算法及其改进的朋友&#xff0c;可关注我的公众号&#xff1a;强盛机器学习&#xff0c;不定期会有很多免费代码分享~ 目录 原理简介 一、种群初始化 二、攻击行为 三…...

sqlmap(四)案例

一、注入DB2 http://124.70.71.251:49431/new_list.php?id1 这是墨者学院里的靶机&#xff0c;地址&#xff1a;https://www.mozhe.cn/ 1.1 测试数据库类型 python sqlmap.py -u "http://124.70.71.251:49431/new_list.php?id1" 1.2 测试用户权限类型 查询选…...

【C++初阶】String在OJ中的使用(一):仅仅反转字母、字符串中的第一个唯一字母、字符串最后一个单词的长度、验证回文串、字符串相加

前言&#xff1a; &#x1f3af;个人博客&#xff1a;Dream_Chaser &#x1f388;博客专栏&#xff1a;C &#x1f4da;本篇内容&#xff1a;仅仅反转字母、字符串中的第一个唯一字母、字符串最后一个单词的长度、验证回文串、字符串相加 目录 917.仅仅反转字母 题目描述&am…...

【25考研】:四川大学计算机学院24届874考研考情分析

去年的考情分析也是我做的&#xff0c; 今年就在去年的基础上做了。保持形式不变&#xff0c;更改数据。 21考情&#xff1a; 万载月寒肠断客&#xff1a;四川大学计算机学院21届CS考研考情分析 22考情&#xff1a; 懒羊羊&#xff1a;四川大学计算机学院2022考研考情分析 2…...

【GPT-4 Turbo】、功能融合:OpenAI 首个开发者大会回顾

GPT-4 Turbo、功能融合&#xff1a;OpenAI 首个开发者大会回顾 就在昨天 2023 年 11 月 6 日&#xff0c;OpenAI 举行了首个开发者大会 DevDay&#xff0c;即使作为目前大语言模型行业的领军者&#xff0c;OpenAI 卷起来可一点都不比同行差。 OpenAI 在大会上不仅公布了新的 …...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...