排列"/>
力扣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、下一个排列
发布评论