一、题目
二、案例
案例一:
输入:nums = [1,2,3]
输出:[1,3,2]
案例二:
输入:nums = [3,2,1]
输出:[1,2,3]
案例三:
输入:nums = [1,1,5]
输出:[1,5,1]
三、思路
由上述题目可知,如果给定数组为降序可知,其不存在最大值,此时我们需要将其降序排列。
如果不为降序数组,我们按照如下方法。这里我们以[3,2,4,1,6,4,0]
为例。1、首先我们应该从后向前遍历,找到第一个降序的值,在该数组中第一个降序的值为 1。
2、然后从后往前找,比1小的值,并且交换位置,此时数组变为:[3,2,4,0,6,4,1]
3、然后再将从0下一位开始,由小到大的顺序排列,由于从6到1是按照从大到小的顺序排列,此时我们可以使用 [nums[x], nums[y]] = [nums[y], nums[x]]
进行交换。
四、代码
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function (nums) {
let length = nums.length
let p = length - 1
while (p > 0 && nums[p] <= nums[p - 1]) {
p--
}
if (p > 0) {
let p2 = length - 1
let curValue = nums[p - 1]
while (p > 0 && p2 > p) {
if (curValue < nums[p2]) {
break
}
p2--
}
[nums[p2], nums[p - 1]] = [nums[p - 1], nums[p2]]
}
let x = p
let y = length - 1
while(x < y) {
[nums[x], nums[y]] = [nums[y], nums[x]]
x++
y--
}
};
五、总结
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_47450807/article/details/123168673
内容来源于网络,如有侵权,请联系作者删除!