实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
思路:
题目要求如果存在下一个更大排列则输出、否则输出最小组合:
抛砖引玉
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function (nums) {
let len = nums.length,
index = len - 2
// 特殊情况如果nums小于两个元素直接返回
if (len < 2) return nums
while (index >= 0 && nums[index] >= nums[index + 1]) {
index--
}
// 倒序遍历中存在递减片段
if (index >= 0) {
let i = len - 1;
// 将递减片段的第一个元素替换到倒序遍历开始的递增片段中
while (i >= 0 && nums[index] >= nums[i]) {
i--
}
[nums[i], nums[index]] = [nums[index], nums[i]]
}
// 翻转已经遍历的递增片段,如果nums整体倒序递增则翻转得到最小组合
reverse(index + 1)
// 翻转指定位置之后的元素
function reverse (index) {
let start = index,
end = len - 1;
while (start < end) {
[nums[start], nums[end]] = [nums[end], nums[start]]
start++
end--
}
}
return nums
};