一、题目
1、算法题目
“将数组序列重新排列成下一个更大的排列，如果不存在下一个更大的排列，则将数组排列成最小的排列。”
题目链接：
来源：力扣（LeetCode）
链接：31. 下一个排列 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1： 输入： nums = [1,2,3] 输出： [1,3,2] 复制代码
示例 2： 输入： nums = [3,2,1] 输出： [1,2,3] 复制代码
示例 3： 输入： nums = [1,1,5] 输出： [1,5,1] 复制代码
示例 4： 输入： nums = [1] 输出： [1] 复制代码
二、解题
1、思路分析
这个题注意到下一个排列总是比当前排列要打，除非该排列已经是最大的排列。
那么，我们可以从后向前查找第一个较小数，此时是下降序列。
找到了顺序对，那么就从后前查找第一个满足的元素，这个元素就是较大数。
交换较小数和较大数，就可以证明这个区间为降序，使用双指针反转区间使其变成升序，则无需对该区间进行排序。
2、代码实现
代码参考：
public class Solution { /// <summary> /// 翻转数组双指针逆序 /// </summary> /// <param name="nums"></param> public void NextPermutation(int[] nums) { int n = nums.Length; //排除特殊情况 if (n <= 1) return; //双指针 int left = n - 2; int right = n - 1; //翻转最小字串 while (right - left < n) { for (int i = right; i >left; i--) { //查询字符串是否可以翻转 if (nums[i]> nums[left]) { //翻转left,i指针 int temp = nums[i]; nums[i] = nums[left]; nums[left] = temp; //翻转left指针后所有项 for (int j = left+1; j <= left+(right-left+1)/2; j++) { temp = nums[j]; nums[j] = nums[right-j+left+1]; nums[right - j + left+1] = temp; } return; } } left--; } //数组顺序翻转数组 for (int i = 0; i < n/2; i++) { int temp = nums[i]; nums[i] = nums[n - 1 - i]; nums[n - 1 - i] = temp; } return; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(N)
其中N为给定序列的长度，我么只需要扫描两次序列，进行一次反转操作。
空间复杂度： O(1)
只需要常数级的空间存放若干变量。
三、总结
这题感觉考的就是数学思维，当思路想明白了，代码也就出来了。
