preface
LeetCode array type problem related solution, can be seen before doing LeetCode array type problem must see, classification solution summary question, can be used to improve each item. If you feel helpful, please remember to pay attention to it. Thank you!
Topic describes
To implement a function that gets the next permutation, the algorithm rearranges the given sequence of numbers into the next larger permutation in the lexicographical order. If no next larger permutation exists, the numbers are rearranged into the smallest permutation (that is, ascending). You must modify in place, allowing only extra constant space.
Example 1: Input: nums = [1,2,3] Output: [1,3,2]
Example 2: input: nums = [3,2,1] output: [1,2,3]
Example 3: input: nums = [1,1,5] output: [1,5,1]
Example 4: Input: nums = [1] Output: [1]
Link: leetcode-cn.com/problems/ne…
Answer key
This solution comes from Imageslr. We can formally describe the problem as: Given a number of numbers, combine them into an integer. How to rearrange the numbers to get the next larger integer. Let’s say 123 and the next bigger number is 132. If there is no larger integer, the smallest integer is printed.
How do you get this sort of order? A. We want the next number to be larger than the current number so that the definition of “next permutation” is satisfied. So you can get a larger number by simply swapping the larger number with the smaller number. For example, 123456. Swap 5 and 6 to get a larger number, 123465. B. The increment of the next number is expected to be as small as possible, so as to meet the requirement that “the next permutation is adjacent to the current permutation”. To satisfy this requirement, we need to swap as far to the right as possible, and we need to look backwards to swap the smallest possible “large number” with the preceding “decimal”. For example, 123465, the next permutation should swap 5 and 4 instead of 6 and 4. After switching the large number to the front, you need to reset everything after the large number to ascending order, which is the smallest permutation. Take 123465 as an example: First, swap 5 and 4 according to the previous step to get 123564; Then you need to reset the number after 5 to ascending order, so you get 123,546. Obviously 123546 is smaller than 123564, so 123546 is the next permutation of 123465.
The algorithm process
- From the back forwardFind the first oneAdjacent ascendingThe elements of
(i,j)
To meet theA[i] < A[j]
. At this time[j,end)
It has to be in descending order - in
[j,end)
From the back forwardFind the first oneA[i] < A[k]
的k
.A[i]
,A[k]
Decimal number large number decimal number - will
A[i]
与A[k]
exchange - You can say that at this point
[j,end)
It has to be in descending order, inverse[j,end)
In ascending order - If no matching pair is found in Step 1, the current value is displayed
[begin,end)
Is a descending order, then jump directly to Step 4
Time complexity O(n)
/ * * *@param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function(nums) {
const n = nums.length
if (n < 2) return nums
/ / find the I
let i = n - 2
while (i >= 0 && nums[i] >= nums[i+1]) --i
// find k and swap I, k
if (i >= 0) {
let k = n - 1
while (nums[i] >= nums[k]) --k
let tmp = nums[i]
nums[i] = nums[k]
nums[k] = tmp
}
// Reverse the part after I
let l = i + 1
let r = n - 1
while (l < r) {
let tmp = nums[l]
nums[l] = nums[r]
nums[r] = tmp
++l
--r
}
};
Copy the code