031.下一个排列Java实现

news/2024/6/16 11:12:29

题意


 

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


 

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。


 

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。


 

如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。


 

  1. 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  2. 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  3. 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。


 

给你一个整数数组 nums ，找出 nums 的下一个排列。


 

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


 

难度


 

中等


 

示例

例1


 

输入：nums=[1,2,3]

输出：[1,3,2]

输入：nums=[3,2,1]

输出：[1,2,3]

输入：nums=[1,1,5]

输出：[1,5,1]


 

分析 1


 

这道题看起来很唬人，比如题目描述中提到的“字典序”，很多人第一眼看到这个名词的时候会有点懵，这里简单解释一下。


 

字典序（dictionary order），又称 字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。


 

在这道题目中，字典序其实是指☞ 数字大小的先后顺序。


 

理解了“字典序”，就能很快理解这道题的题意了：要我们求出比这个数更大的一个排列，比如 123，比它大的是 132，对吧？只需要改变 23 的位置就可以了。312 也比 123 大，只不过它是比 132 更大的一个，不是比 123 更大的一个，官大一级压死人，一级一级来压（😂）。


就好像我们在打扑克牌，我出了一个对 10，那你出对 11 就压住我了，没必要把手里的对 12 先出来，对吧？


 

再比如 321 已经是「1、2、3」 这三个数字组合中最大的那个了，那就等于说没有更大的了，所以返回 123 这个最小的。


 

明白了吧？


 

要想解题，首先得明白题意，所以语文理解是非常重要的，其次是经验（😁）。


 

那凭借我们以往的经验，可能一下子会想到全排列。就拿 1、2、3、4 来举例吧，全排列如下：


nums=[1,2,3,4]

nums=[1,2,4,3]

nums=[1,3,2,4]

nums=[1,3,4,2]

nums=[1,4,2,3]

nums=[1,4,3,2]

nums=[2,1,3,4]

nums=[2,1,4,3]

nums=[2,3,1,4]

nums=[2,3,4,1]

nums=[2,4,1,3]

nums=[2,4,3,1]

nums=[3,1,2,4]

nums=[3,1,4,2]

nums=[3,2,1,4]

nums=[3,2,4,1]

nums=[3,4,1,2]

nums=[3,4,2,1]

nums=[4,1,2,3]

nums=[4,1,3,2]

nums=[4,2,1,3]

nums=[4,2,3,1]

nums=[4,3,1,2]

nums=[4,3,2,1]

观察nums = [1,3,4,2] -> nums = [1,4,2,3]这一步，因为4比3大，且4的位置在3之后，所以将4与3交换，必然能够使得nums变大，交换了之后，则变成了nums = [1,4,3,2]。


 

但显然这不是最小的比nums = [1,3,4,2]大的一个排列，我们还要把3和2的位置再翻转一下，才能得到nums = [1,4,2,3]这个 恰好 比nums = [1,3,4,2]大一点的排列。


 

那到底该怎么去找到这个 恰好 比nums大一点的排列呢？

第一步，我们可以从右向左查找第一个升序的相邻数字对 (i, i+1)，满足 nums[i] < nums[i+1]。


 

这意味着从 i+1 到末尾的数字都是降序的。如果找不到这样的 i（即整个数组是降序的），这说明当前排列已经是最大的排列，我们只需将其翻转为最小排列即可。

这一步完成之后，并不能保证我们得到的排列就是 恰好 比nums大一点的排列。

这一步完成之后，并不能保证我们得到的排列就是 恰好 比nums大一点的排列。


 

第二步，我们还要对nums[i+1] 到 nums[nums.length - 1]这个区间进行翻转，使得它变成升序排列，这样才能得到 恰好 比nums大一点的排列。


 

比如说上面提到的 [1,4,3,2]，i+1（i=1）到末尾的部分是 32。这部分是降序的。为了得到下一个排列，我们需要这部分变成升序。我们需要将这部分翻转，变成 23。

所以到这里，这道题目就迎刃而解了。具体代码实现：

class Solution {public void nextPermutation(int[] nums) {// 步骤1：从右向左查找第一个升序的相邻数字对(i, i+1)，满足nums[i] < nums[i+1]。int i = nums.length - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}if (i >= 0) {// 步骤2：在nums[i+1:]中从右向左找到第一个大于nums[i]的数字nums[j]。int j = nums.length - 1;while (j >= 0 && nums[i] >= nums[j]) {j--;}// 步骤3：交换nums[i]和nums[j]。swap(nums, i, j);}// 步骤4：将nums[i+1:]翻转，使其变为升序。reverse(nums, i + 1);}// 用于交换数组中两个元素的位置private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}// 用于将数组的一部分翻转，即将nums[start:]变为升序private void reverse(int[] nums, int start) {int end = nums.length - 1;while (start < end) {swap(nums, start, end);start++;end--;}}
}


为了更清晰地理解题解代码，我们将其拆分成几个关键部分，并逐一说明每部分的作用和逻辑。


 

1.寻找升序对 (i, i+1)
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {i--;
}

  1. 目的：从数组的右端开始向左扫描，寻找第一个升序的相邻数字对，即找到第一个nums[i] < nums[i + 1]的位置。这个位置i是需要进行调整的起点，因为nums[i]右边的序列是降序的，没有更大的排列空间。
  2. 逻辑：使用一个while循环从右向左遍历数组，直到找到满足升序条件的i。


 

2.在 nums[i+1:] 中找到第一个大于 nums[i] 的数字并交换


 

nums[i+1:] 是指从i+1到数组末尾的部分。

if (i >= 0) {int j = nums.length - 1;while (j >= 0 && nums[i] >= nums[j]) {j--;}swap(nums, i, j);
}

  1. 目的：如果找到了这样的i，则在其右侧找到第一个大于nums[i]的数字nums[j]，然后交换nums[i]和nums[j]。这一步是为了在当前排列的基础上得到下一个稍大的数字。
  2. 逻辑：通过向左扫描数组的剩余部分来查找j，一旦找到就执行交换。


 

3.翻转 nums[i+1:] 使其升序

reverse(nums, i + 1);

  1. 目的：交换nums[i]和nums[j]后，i之后的序列仍然保持降序。为了获得下一个排列，需要将这个序列翻转成升序，这样从i+1到数组末尾就构成了最小的排列，确保整个数组是下一个更大的排列。
  2. 逻辑：从i+1开始到数组末尾，执行翻转操作，使其成为升序。


 

4.交换方法 swap

private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;
}

交换数组中两个位置的元素。


 

5.翻转方法 reverse

private void reverse(int[] nums, int start) {int end = nums.length - 1;while (start < end) {swap(nums, start, end);start++;end--;}
}

将数组从指定位置start到数组末尾的部分翻转，使其成为升序。

测试：


/*** @ClAssName NextPermutation* @Description* 输入：nums=[1,2,3]* 输出：[1,3,2]* 输入：nums=[3,2,1]* 输出：[1,2,3]* 输入：nums=[1,1,5]* 输出：[1,5,1]* @Author 欧妮甲是神仙* @Date 2024/5/11 17:{MINUTE}*/
public class NextPermutation {public static void main(String[] args) {int[] nums = {1,3,4,2};nextPermutation(nums);System.out.println(Arrays.toString(nums));}static void  nextPermutation(int[] nums){//1、从右向左查找到第一个升序的相邻数字（i， i+ 1） ，满足 nums[i] < nums[i +1] .//那么一直找的条件是 反过来的， num[i]  > num[i +1]int i = nums.length -2;   ///表示倒数第二个数 ，如果为倒数第一个数， nums[i] >= nums[i+1] ，这里会数组越界while (i >=0 && nums[i] >= nums[i+1]){i--;}//找到定位的i之后if (i >=0){//2、在num[i+1]中从右向左找到第一个大于num[i]的数字num[j].。int j = nums.length-1;while (j >=0 && nums[i] >=nums[j]){j--;}//3、交换num[i]和num[j]swap(nums ,i , j);}//4、将num[i+1]翻转，使其变为升序revers(nums , i +1);}private static void  swap(int[] nums, int i, int j){int temp = 0;temp = nums[i];nums[i] = nums[j];nums[j] = temp;}//用于将数组的一部分翻转，即将nums[start] 变为升序private static void  revers(int[] nums, int start){int end = nums.length-1;while (start < end){swap(nums , start ,end);start++;end--;}}}


 

效率嘛，自然是快得飞起。

总结


 

这道题目的难点其实在于字典序的理解，一旦理解之后，整个题目的解法就不算是特别难了。


题目链接地址：

. - 力扣（LeetCode）


http://www.mrgr.cn/p/04637724

相关文章

【资源分享】野比大雄的生化危机宫格解密工具

【资源分享】野比大雄的生化危机宫格解密工具

一款简单的游戏工具*----------------------------------------------[下载区]----------------------------------------------* 蓝奏云（提取码：ysgg） *----------------------------------------------[下载区]----------------------------------------------**---------…
阅读更多...
pwn知识——劫持IO-file_jumps攻击和environ攻击

pwn知识——劫持IO-file_jumps攻击和environ攻击

导言 哎，异或fd指针真是令人讨厌 IO_file_jumps _IO_lock_t _IO_stdfile，_IO_wide_data（针对宽字节的虚函数表），_IO_FILE_plus（含有stdin,stdout）三者均被定义为IO_file_jumps 原理 IO_file_jumps是一个全局变量符号，存有以下符号这个结构体主要跟缓冲区有关，比如调用…
阅读更多...
堆排序 之实现最小的K个数

堆排序 之实现最小的K个数

目录 1、方式一&#xff1a;通过自定义实现建堆和堆化操作 2、方式二&#xff1a;借助模块heapq实现 2.1、模块heapq的基本使用 2.2、使用heapq实现最小的k个数 3、堆在实际项目的应用 实现语言&#xff1a;Python 3.9 题目来源&#xff1a;牛客 分析&#xff1a; 要找…
阅读更多...
示例七、超声波传感器测距

示例七、超声波传感器测距

通过以下几个示例来具体展开学习,了解超声波传感器原理及特性&#xff0c;学习超声波传感器的应用&#xff1a; 示例七、超声波传感器测距 一、基本原理&#xff1a; 1、超声波测距仪的系统结构 利用超声测距原理测量物体之间的距离&#xff0c;当此距离小于某一设定值时&…
阅读更多...
嵌入式软硬件设计流程

嵌入式软硬件设计流程

转载自：https://blog.csdn.net/jiangjunjie_2005/article/details/44024933从图书馆看到一经典国外嵌入式设计书籍，其中关于“软硬件设计流程”画得精彩，特列出如下：
阅读更多...
ctfshow web入门 php反序列化 web267--web270

ctfshow web入门 php反序列化 web267--web270

web267 查看源代码发现这三个页面 然后发现登录页面直接admin/admin登录成功 然后看到了 ///backdoor/shell unserialize(base64_decode($_GET[code]))EXP <?php namespace yii\rest{class IndexAction{public $checkAccess;public $id;public function __construct(){…
阅读更多...
WPF 基础、WPF 相关知识、学习、参考项目

WPF 基础、WPF 相关知识、学习、参考项目

前言：最初参加工作时，做过WPF项目 ，后面几年后者虽然有写WPF项目，但多数都是边边角角，写一点满足工作需要。现在写下WPF，主要就是玩一玩，尝试下不同的东西。这是我的代码仓库：地址 （如果对您有帮助，给颗小星星奖励下吧），在WPF/Lesson 10 Practice/Practice/下面。基…
阅读更多...
Rust Course学习（编写测试）

Rust Course学习（编写测试）

如果友友你的计算机上没有安装Rust&#xff0c;可以直接安装&#xff1a;Rust 程序设计语言 (rust-lang.org)https://www.rust-lang.org/zh-CN/ Introduce 介绍 Testing in Rust involves writing code specifically designed to verify that other code works as expected. It…
阅读更多...
WPF 整体结构基础

WPF 整体结构基础

前言：最初参加工作时，做过WPF项目 ，后面几年后者虽然有写WPF项目，但多数都是边边角角，写一点满足工作需要。现在写下WPF，主要就是玩一玩，尝试下不同的东西。这是我的代码仓库：地址 （如果对您有帮助，给颗小星星奖励下吧），在WPF/Lesson 10 Practice/Practice/下面。基…
阅读更多...
使用Django中的Session和Cookie来传递数据

使用Django中的Session和Cookie来传递数据

在Django中&#xff0c;Session和Cookie是两种常用的机制&#xff0c;用于在服务器端和客户端之间传递数据。下面我将简要介绍如何在Django中使用Session和Cookie来传递数据。 1、问题背景 在 Django 中&#xff0c;可以使用 request.POST 来获取表单提交的数据。但是&#xf…
阅读更多...
最新ChatGPT中文系统网站源码+系统部署+支持AI对话、AI绘画、AI音乐等大模型

最新ChatGPT中文系统网站源码+系统部署+支持AI对话、AI绘画、AI音乐等大模型

一、系统介绍 本文将介绍最新的ChatGPT中文版AI创作系统——星河易创AI系统&#xff0c;该系统基于ChatGPT的核心技术&#xff0c;融合了自然语言问答、绘画、音乐等创作功能&#xff0c;并兼容官方GPT全模型。该系统提供多样化的应用&#xff0c;包括GPTs的多场景应用、实时G…
阅读更多...
布局全球内容生态，酷开科技Coolita AIOS以硬核品质亮相

布局全球内容生态，酷开科技Coolita AIOS以硬核品质亮相

当前&#xff0c;全球产业链供应链格局持续重构&#xff0c;成为影响中国对外经济发展的重要因素。2024年4月15至5月5日&#xff0c;历史久、规模大、层次高&#xff0c;作为中国外贸风向标的第135届中国进出口商品交易会&#xff08;即广交会&#xff09;在美丽的广州隆重举行…
阅读更多...
CLI举例：通过URL分类控制用户访问的网站

CLI举例：通过URL分类控制用户访问的网站

华为CLI举例&#xff1a;通过URL分类控制用户访问的网站 配置基于URL分类的URL过滤功能&#xff0c;可以实现对用户访问的某一类网站的控制。既可以是FW自带的预定义分类&#xff0c;也可以是管理员配置的自定义分类。 组网需求 如图1所示&#xff0c;FW作为企业网关部署在网络…
阅读更多...
Spring如何解决循环依赖问题？

Spring如何解决循环依赖问题？

当然是用三级缓存来解决循环依赖问题。 那二级缓存能解决吗&#xff1f; 首先我们要知道Spring bean的生命周期 1.实例化&#xff08;new&#xff09; 2.属性赋值&#xff08;populate&#xff09; 3.初始化 一堆钩子函数&#xff08;动态代理的生成也在这一步&#xff09…
阅读更多...
【机器学习】卷积神经（CNN）在图像识别中的革命性应用：自动驾驶的崛起

【机器学习】卷积神经（CNN）在图像识别中的革命性应用：自动驾驶的崛起

卷积神经网络&#xff08;CNN&#xff09;在图像识别中的革命性应用&#xff1a;自动驾驶的崛起 一、卷积神经网络&#xff08;CNN&#xff09;的基本原理二、CNN在图像识别中的显著成果三、CNN在自动驾驶汽车中的物体检测和识别四、CNN在图像识别中的代码实例 随着人工智能和深…
阅读更多...
一、RocketMQ基本概述与部署

一、RocketMQ基本概述与部署

RocketMQ基本概述与安装 一、概述1.MQ概述1.1 用途1.2 常见MQ产品1.3 MQ常用的协议 2.RocketMQ概述2.1 发展历程 二、相关概念1.基本概念1.1 消息&#xff08;Message&#xff09;1.2 主题&#xff08;Topic&#xff09;1.3 标签&#xff08;Tag&#xff09;1.4 队列&#xff0…
阅读更多...
鸿蒙内核源码分析(文件句柄篇) | 你为什么叫句柄

鸿蒙内核源码分析(文件句柄篇) | 你为什么叫句柄

句柄 | handle int open(const char* pathname,int flags); ssize_t read(int fd, void *buf, size_t count); ssize_t write(int fd, const void *buf, size_t count); int close(int fd);只要写过应用程序代码操作过文件不会陌生这几个函数,文件操作的几个关键步骤嘛,跟把大…
阅读更多...
智能工作流：Spring AI高效批量化提示访问方案

智能工作流：Spring AI高效批量化提示访问方案

集用SpringAI搭建系统，依靠线程池\负载均衡等技术进行请求优化，用于解决科研&开发过程中对GPT接口进行批量化接口请求中出现的问题。大语言模型接口以OpenAI的GPT 3.5为例，JDK版本为17。基于SpringAI搭建系统，依靠线程池\负载均衡等技术进行请求优化，用于解决科研&…
阅读更多...
【小白可懂】SpringBootWeb入门

【小白可懂】SpringBootWeb入门

web开发需要的技术栈&#xff1a; 前端web开发&#xff1a; html css javascript Vue Element Nginx 后端web开发&#xff1a; Maven SpringBoot Web 基础篇 MySOL SpringBoot Mybatis SpringBoot Web开发篇 SpringBoot web进阶篇 什么是spring&#xff1f; 官网&a…
阅读更多...
修改el-checkbox样式

修改el-checkbox样式

一定要在最外层&#xff1b; //未选中框/deep/ .el-checkbox__inner{border-color: #0862a3;}//选中框/deep/ .el-checkbox__input.is-checked .el-checkbox__inner{background-color: #0862a3;border-color: #0862a3;}//未选中框时右侧文字/deep/ .el-checkbox__label{}//选中…
阅读更多...
推荐文章

Copyright @ 2022~2023