gpt4 book ai didi

Java全排列算法字典序下的下一个排列讲解

转载 作者:qq735679552 更新时间:2022-09-28 22:32:09 27 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java全排列算法字典序下的下一个排列讲解由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

一直写过数组全排列的算法,当时接触的是使用回溯的方法,这样可以保证生成的全排列一定是按照字典序的,但是今天在做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了.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 。

最后此篇关于Java全排列算法字典序下的下一个排列讲解的文章就讲到这里了,如果你想了解更多关于Java全排列算法字典序下的下一个排列讲解的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com