力扣31、下一个排列

编程入门 行业动态 更新时间:2024-10-27 07:19:04

力扣31、下一个<a href=https://www.elefans.com/category/jswz/34/1771131.html style=排列"/>

力扣31、下一个排列

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。必须原地修改,只允许使用额外常数空间。以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

字典序的意思是啥?我想了很长时间,说白了就是
把数组当做一个数字,重新排序后,要求比初试的数字只大一点,
从123—》132,而不是直接到213,231,312,321,这样更大的数字
那么如果一开始就是最大的数字咋整?
我们需要将数字重新排列成最小的排列,即321–》123
好了
题意清楚了我们来想下思路吧。
思路思路
come on baby
出现吧
巴拉巴拉小魔仙
那么若是不存在变大的可能的话,也就是从左到右每个左边的都比右边的大,那么我们排成最小的就好了
若是有变大的可能,那么我们需要找出最右部分,注意是部分,是一个范围内,出现i<i-1;但是i-1>一直到数组最后。
这就是我们需要找到的突破点。
我们找的代码,如下。

          boolean flag=true;int pos=0;for(int i=0;i<nums.length-1;i++){if(nums[i]>=nums[i+1])//左边的都比右边的大continue;if(nums[i]<nums[i+1]){pos=i+1;//最右部分flag=false; 		}   		 }if(flag)Arrays.sort(nums);//不存在变大的可能的话

那么我们做完这一步
是不是单纯的把突变的那一块换掉,然后从pos往后按照从小到大的顺序排列就行了??

我告诉你,你想多了
我为嘛知道?
因为我试了。。。。
哈哈哈哈
菜鸡了吧

其实还有一个细节,这个细节就是
我们怎么能确定pos位置之后的数都比pos-1位置的数小呢?
存在着这么一种数,它的大小比pos-1的稍微大一点,但是它的右边都比pos-1小,左边
都大于pos-1 一直到pos
所以我们需要找到这个数
从此之后就没有问题啦。
完整代码如下:

public class M31nextPar {public static void nextPermutation(int[] nums) {boolean flag = true;int pos = 0;for (int i = 0; i < nums.length - 1; i++) {if (nums[i] >= nums[i + 1])continue;if (nums[i] < nums[i + 1]) {pos = i + 1;flag = false;}}if (flag)Arrays.sort(nums);else {if (pos == nums.length - 1) {swap(nums, pos, pos - 1);} else {int max = nums[pos];int i = pos;int pos2 = pos;for (; i < nums.length; i++) {if (nums[i] <= max && nums[i] > nums[pos - 1]) {max = nums[i];//存在着这么一种数,它的大小比pos-1的稍微大一点,但是它的右边都比pos-1小,左边都大于pos-1 一直到pospos2 = i;}}swap(nums, pos2, pos - 1);Arrays.sort(nums, pos, nums.length);}}}private static void swap(int[] nums, int pos, int i) {int k = nums[i];nums[i] = nums[pos];nums[pos] = k;}public static void main(String[] args) {int[] nums = { 1, 3, 2 };nextPermutation(nums);for (int i : nums)System.out.println(i);}
}

okok,如果你看到这,觉得对你有所帮助的话,关注点下。谢谢老铁的关注和红心咯。。。

更多推荐

力扣31、下一个排列

本文发布于:2024-03-10 01:28:24,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1726668.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:排列   力扣

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!