“将数组序列重新排列成下一个更大的排列,如果不存在下一个更大的排列,则将数组排列成最小的排列。”
题目链接:
来源:力扣(LeetCode)
链接:31. 下一个排列 - 力扣(LeetCode) (leetcode-cn.com)
实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列(即,组合出下一个更大的整数)。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
示例 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]
这个题注意到下一个排列总是比当前排列要打,除非该排列已经是最大的排列。
那么,我们可以从后向前查找第一个较小数,此时是下降序列。
找到了顺序对,那么就从后前查找第一个满足的元素,这个元素就是较大数。
交换较小数和较大数,就可以证明这个区间为降序,使用双指针反转区间使其变成升序,则无需对该区间进行排序。
代码参考:
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;
}
}
时间复杂度 : O(N)
其中N为给定序列的长度,我么只需要扫描两次序列,进行一次反转操作。
空间复杂度: O(1)
只需要常数级的空间存放若干变量。
这题感觉考的就是数学思维,当思路想明白了,代码也就出来了。