Next Permutation (M)
題目
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
題意
按照字典序，輸出當前數字序列的下一個排序，如果已經是遞減數列，則回傳遞增數列，
思路
對于一個任意元素不相同的序列來說，正序排列是最小的排列方式，相應的逆序排列是最大的排列方式，以整數序列{1, 2, 3}為例，{1, 2, 3}是第一個排列，{3, 2, 1}則是最后一個排列，明確這一點才能展開下面的分析，
從序列末尾向前查找，直到第一次出現nums[i - 1] < nums[i]，這說明第i及i之后的數為逆序排列，已達到該子序列的最大排列方式，需要更新該子序列前一位數字(即nums[i - 1])，這時只要從末尾查找，將第一個比nums[i - 1]大的數與nums[i - 1]交換，再將i及i之后的數字逆序，即可得到下一個排列，
代碼實作
Java
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 1;
while (i >= 1 && nums[i] <= nums[i - 1]) {
i--;
}
if (i == 0) {
reverse(nums, 0, nums.length - 1);
} else {
int j = nums.length - 1;
while (nums[j] <= nums[i - 1]) {
j--;
}
int temp = nums[i - 1];
nums[i - 1] = nums[j];
nums[j] = temp;
reverse(nums, i, nums.length - 1);
}
}
private void reverse(int[] nums, int i, int j) {
while (i <= j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
}
}
JavaScript
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function (nums) {
let p = nums.length - 1
while (p > 0 && nums[p - 1] >= nums[p]) {
p--
}
if (p === 0) {
nums.reverse()
return
} else {
let q = nums.length - 1
while (nums[p - 1] >= nums[q]) {
q--
}
[nums[p - 1], nums[q]] = [nums[q], nums[p - 1]]
q = nums.length - 1
while (p < q) {
[nums[p++], nums[q--]] = [nums[q], nums[p]]
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/38856.html
標籤：其他