做网站需要域名 域名是啥,互联网编程,农村工作会议2022全文,个人介绍网页制作实现获取下一个排列的函数#xff0c;算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列#xff0c;则将数字重新排列成最小的排列#xff08;即升序排列#xff09;。
必须原地修改#xff0c;只允许使用额外常数空间。
以下是…实现获取下一个排列的函数算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列则将数字重新排列成最小的排列即升序排列。
必须原地修改只允许使用额外常数空间。
以下是一些例子输入位于左侧列其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 分析
这道题如果暴力解法的话需要将可能的排列都写出来并且用数组存储起来不论是时间复杂度亦或是空间复杂度都是不客观的。
可以通过一次遍历完成从后向前遍历
如果后面的值一直比前面与他相邻的值大那就说明目前的排序已经是最大值我们按照题目需求逆置数组即可
例如7654321965
如果后面的值比前面的值大时将前面这个位置记录下来可以用x来表示之后将x后面的所有值中大于x但是最接近x的值与x进行交换。
例如115-151 4756-4765
但是这里有一个问题对于一些排列无法得到想要的结果
例如1765432-2765431 ,可以看到比1765432大的下一个数字应该是2176543明显得到了错误的答案
因此我们需要加一步操作在交换之后对x之后的元素进行一次排序使之变为升序排序 代码如下
import java.util.Arrays;
public class Solution31 { public static void nextPermutation(int[] nums) { int i,j,t,flag0,min,k0; //flag是用来记录当前序列是否为最大的序列如果是其值为0反之为1 int n nums.length; for(in-1;i1;i--) { if(nums[i]nums[i-1]) { flag 1; break; } } if(flag1) { min nums[i]; k i; for(ji;jn;j) { if(nums[j]minnums[j]nums[i-1]) { min nums[j]; k j; } } t nums[i-1]; nums[i-1] nums[k]; nums[k] t; Arrays.sort(nums, i, nums.length); } else { for(i0;in/2;i) { t nums[i]; nums[i] nums[n-i-1]; nums[n-i-1] t; } } for(i0;in;i) { System.out.println(nums[i]); } } public static void main(String[] args) { //int[] nums {1,1,5}; //int[] nums {3,2,1}; //int[] nums {1,2,3}; //int[] nums {1,3,2}; //int[] nums {1,7,6,5,4,3,2}; //int[] nums {2,3,1}; int[] nums {5,4,7,5,3,2}; nextPermutation(nums); } }
