Java全排列算法字典序下的下一个排列讲解
作者:chaoweilanmaohhh 发布时间:2023-07-30 17:44:39
一直写过数组全排列的算法,当时接触的是使用回溯的方法,这样可以保证生成的全排列一定是按照字典序的,但是今天在做leetcode上的一道题时,问题是要你找到某个排列情况的下一个按照字典序排列的状态。
如果直接一点,大可从头开始做全排列,然后到目标状态时,在做一次即可找到要的状态,但是如果题目给的状态非常靠后,则要花费很大的代价,这样做就显得有些笨拙了。
所以做这道题的时候一直在思考如何按照字典序生成全排列。
假设此时给出的状态时5 2 4 3 1,那么下一个状态要如何确定呢?首先从人的视角来看,绝对会从序列末尾向前开始查找,例如如果给的状态时1 2 3 4 5,则很容易发现下一个状态应该是1 2 3 5 4,这样就给出了一个策略,第一步应该先找从末尾开始向前第一对非逆序数对,这当然有理由,因为如果是逆序的,说明该种情况一定是已经进行过交换了,则绝对不会是下一种情况交换的候选位置,因此会发现5 2 4 3 1中第一个非逆序数对是2 4,所以交换的候选对象应该是2(2是较小的那一个);紧接着继续思考,应该和后面的哪一个进行交换。首先显而易见的是,2后面的子序列一定是逆序的。那么如果要和2交换并且使结果是字典序的下一个的话,那么与2交换的一定是2后面的比2大的最小的哪一个数,因此第二步就是从序列末尾开始向前查找第一个比2大的数,与2进行交换(此时为 5 3 4 2 1),那么下一步也是显而易见的,3后面的序列应该是由5 3开始的字典序最小的一个序列,因此要将3后面的序列逆置。最后得到答案5 3 1 2 4。
过程并不复杂,思路和人思考的顺序应该是一样的,直接上coding了。
public void reverse(int []nums,int l,int r){
while(l<r){
int tmp=nums[l];
nums[l]=nums[r];
nums[r]=tmp;
l++;
r--;
}
}
public void nextPermutation(int[] nums) {
if(nums.length==0||nums.length==1) return;
int i=nums.length-1;
for(;i>=1;i--){
if(nums[i]>nums[i-1])
break;
}
if(i==0){
Arrays.sort(nums);
return;
}
int index=i-1;
int diff=nums[i-1];
for(i=nums.length-1;i>=0;i--){
if(nums[i]>diff)
break;
}
int tmp=nums[index];
nums[index]=nums[i];
nums[i]=tmp;
reverse(nums,index+1,nums.length-1);
}
来源:https://blog.csdn.net/chaoweilanmaohhh/article/details/79690453
猜你喜欢
- 概述递归:指在当前方法内调用自己的这种现象。递归的分类:递归分为两种,直接递归和间接递归。直接递归称为方法自身调用自己。间接递归可以A方法调
- 本文实例为大家分享了Unity2D游戏回旋镖实现的具体代码,供大家参考,具体内容如下以下我举出2种同使用情况的回旋镖那么回旋镖需要怎么做呢?
- 1 原码、反码、补码原码:将十进制转化为二进制即原码;反码:正数的反码与原码相同,负数的反码(除却最高位的符号位不变)与原码相反
- 目录1.概览2.自定义枚举方法3.使用 == 比较枚举类型4.在 switch 语句中使用枚举类型5.枚举类型的属性,方法和构造函数6.En
- Map集合和Collection集合的区别Map集合是有Key和Value的,Collection集合是只有Value。Collection
- WCF实例(带步骤) <xmlnamespace prefix ="o" ns ="urn:schema
- 1.代码:import java.math.BigDecimal;import java.text.DecimalFormat;import
- 著名的Java单元测试框架Junit 4已经出来很长时间了,当时我发现JUnit 5已经处于测试版,就准备写文章来介绍JUnit 5.不过因
- 本文实例分析了Java接口默认方法带来的问题。分享给大家供大家参考,具体如下:一 点睛Java 8中,如果一个类实现两个或多个接口,即“变相
- 效果展示人脸支付效果视频密码框输入支付效果视频因为密码支付时会调起系统安全键盘,开启自动保护功能,防止泄露,会导致输入密码时录屏黑屏,故使用
- Java 线程池ExecutorService1.线程池1.1什么情况下使用线程池单个任务处理的时间比较短.将需处理的任务的数量大.1.2使
- sidebarDepth: 3条件构造器说明以下出现的第一个入参boolean condition表示该条件是否加入最后生成的SQL中,例如
- 本文实例为大家分享了Java实现24点小游戏的具体代码,供大家参考,具体内容如下程序设计要求:24点游戏是经典的纸牌益智游戏。常见游戏规则:
- 我就废话不多说了,大家还是直接看代码吧~//执行的是删除信息的操作 String a=request.getParameter("
- 前言在看一本关于高性能编程的时候发现 Java8 中关于接口的新特性的介绍,这个特性是真的棒,解决了一个接口中有多个方法,但并不想实现该接口
- 我就废话不多说了,大家还是直接看代码吧!public static String mapToTxt(Map<String,String
- 一、前言我们经常会接触各种池化的技术或者概念,包括对象池、连接池、线程池等,池化技术最大的好处就是实现对象的重复利用,尤其是创建和使用大对象
- 一、连接数据库的配置单独放在一个properties文件中之前,我们是直接将数据库的连接配置信息写在了MyBatis的conf.xml文件中
- 目录1. List1.1 List 的常见方法1.2 代码示例2. ArrayList2.1 介绍2.2 ArrayList 的构造方法2.
- strcpy函数详解如下1.函数介绍1.1.函数接口char * __cdecl strcpy(char * dst, const char