算法题解记录31+++下一个排列（百题筑基）

本文主要是介绍算法题解记录31+++下一个排列（百题筑基），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我是蚊子码农，本次为大家带来一道“双指针”题目。

一、题目描述

题目难度：中等。
整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

二、解题准备（朴素方案）

第一，题意理解

本题的题目相对复杂，我们可以这样理解。
对于一组由数字组成的数组，按照数字大小的顺序，它们会有n多种排列结构。
比如数组【1，2，3】，会存在这样的排列
【1，2，3】，【1，3，2】，【2，1，3】，【2，3，1】，【3，1，2】，【3，2，1】
可以看出，从小到大的排序，是第一个序列。
从大到小的排序，是最后一个序列。

第二，排列之间的关系

对于一个排列来说，它符合这样的特点（忽略最后一个序列【即从大到小】）
首先，从某个下标开始，后面的数，都是从大到小排序。
例如【1，3，5，4，2】
可以看到，从3开始，【5， 4， 2】组成一个从大到小的排序；
可以看出，假使以（2，4，5）作为一个数组，那么，【5，4，2】明显是最大的数组了。
它的下一个序列，只能是倒序的【2，4，5】
其次，从3的视角看，序列【3，5，4，2】的下一个序列，明显是【4，2，3，5】
可以看出，其结构就是数字3与数字4做了交换，并且倒序输出后面的3个数字。
这里需要好好阅读，因为序列的概念有些不好理解。

第三，概念定义

我们可以定义这样的概念，最大序列数组。
它表示，在一个数组中，从某个下标k开始，后面的所有数字，都是按照从大到小的顺序，进行组合的。
比如【1，3，5，4，2】中的数组【5，4，2】
或者另外的【1，4，5，3，2】中的【5，3，2】
另外，我们定义这个概念，极小数
极小数表示，以最大序列数组的前缀数值（即前一个数）为标准，在最大序列数组中，比前缀数大，但是在最大序列数组中最小的数。
有了这两个概念，我们就可以解题了。

三、解题方案

其实经过前面的铺垫，解题方案就呼之欲出了，在此不解释。
首先，介绍两个技巧，如何倒序输出后半段数组，以及如何得到最大序数组。

第一，倒序输出后半段数组。

不考虑“后半段”这个概念，倒序输出数组，可以使用双指针。
具体是这样，使用头指针head指向下标0，尾指针tail指向len-1。【len表示数组长度】
交换头尾指针的数值，完成一次交换，然后head++，tail–。
这样迭代，直到交换len➗2次。
使用len除以2次的原因，是假如一个数组有4位，需要交换2次，满足len除以2。
假如一个数组有5位，中间的数不需要交换，刚好也是len除以2次。【切记，int相除会取整】
考虑“后半段”概念，也就是说，我们需要倒序输出，从某个下标k开始的，后半段数组。
其实非常类似，我们只需要把后半段数组当成正常的数组操作即可。
使得头指针head指向下标k。
尾指针tail指向len-1。
一共需要交换len-k除以2次。

第二，如何得到最大序数组？

这句话意义不太明确，其实是这样的。
我们希望知道，怎么判断一个数组，是不是最大序数组？
可以使用双指针。
假如一个数组只有1个元素，不必判断，一定是最大序数组。
假如一个数组有2个元素，则判断1次。
假如有n个元素，则需要判断n-1次。
首先使得头指针head指向0，next指针指向1。
判断head是否大于next，假如大于，则满足局部最大序。
假如等于或小于，说明不满足。
当然，从前往后的朴素思路，明显无法解决下一个排列的问题。
我们可以从本题出发，从后往前开始。
使得尾指针tail指向len-1，next指针指向len-2。
假使tail指针大于next指针，说明不满足最大序。
此时，正好是我们需要重新排序的时候。
只需要交换极小数和next指针指向的对象，然后把最大序数组倒序输出，即可得到答案。

四、代码（答案）

class Solution {public void nextPermutation(int[] nums) {int len = nums.length;// 假如长度只为1if(len <= 1){return;}// 双指针int next = len-1;int fore = len -2;// 比较len-1次for(int i=0; i<len-1; i++){// 假如后比前大，说明转化后，是下一个排列if(nums[next] > nums[fore]){// 与最大序数组中 最小但是大于前缀 的数值交换while( next<len && nums[next] > nums[fore] ){next++;}// 极值点next--;// 交换int temp = nums[next];nums[next] = nums[fore];nums[fore] = temp;// 最大序倒序输出reverseSome(nums, fore);break;}// 假如0和1比较了，说明没有更大排列，直接倒序输出if(fore == 0){reverse(nums);        break;}next--;fore--;}}private void reverseSome(int[] nums, int fore){// 从fore的下一个开始，一直到结尾int fir = fore + 1;int len =nums.length;int sec = len-1;int tmLen = len - fir;// 最多交换len/2次for(int i=0; i<tmLen/2; i++){int temp = nums[fir];nums[fir] = nums[sec];nums[sec] = temp;fir++;sec--;}}private void reverse(int[] nums){int fir = 0;int sec = nums.length-1;// 最多交换len/2次for(int i=0; i<nums.length/2; i++){int temp = nums[fir];nums[fir] = nums[sec];nums[sec] = temp;fir++;sec--;}}
}