31. Next Permutation
排列是將一個整數數組的成員安排成一個序列或線性順序。
例如，對於數組 arr = [1,2,3]，所有排列為：[1,2,3]， [1,3,2]， [2,1,3]， [2,3,1]， [3,1,2]， [3,2,1]。
一個整數數組的下一個排列是其整數的下一個按字典序排列的更大排列。更正式地說，如果將數組的所有排列按字典序順序排序，那麼該數組的下一個排列就是排序容器中緊跟其後的排列。如果這種排列不可能，則必須將數組重新排列為最低可能的順序（即按升序排序）。
例如，arr = [1,2,3] 的下一個排列是 [1,3,2]。 類似地，arr = [2,3,1] 的下一個排列是 [3,1,2]。 而 arr = [3,2,1] 的下一個排列是 [1,2,3]，因為 [3,2,1] 沒有更大的字典序排列。 給定一個整數數組 nums，找到 nums 的下一個排列。
替換必須就地進行，只使用常數級額外內存。
範例 1：
輸入：nums = [1,2,3] 輸出：[1,3,2]
Python
from typing import List
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
if n <= 1:
return
# Step 1: Find the largest index `i` such that nums[i] < nums[i + 1]
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
# Step 2: Find the largest index `j` such that nums[i] < nums[j]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# Step 3: Swap nums[i] and nums[j]
nums[i], nums[j] = nums[j], nums[i]
# Step 4: Reverse the sequence from nums[i + 1] to the end
self.reverse(nums, i + 1, n - 1)
def reverse(self, nums: List[int], start: int, end: int) -> None:
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
16.38MB, 42ms
C++
#include <vector>
#include <algorithm> // for std::reverse
using namespace std;
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
if (n <= 1) {
return;
}
// Step 1: Find the largest index `i` such that nums[i] < nums[i + 1]
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
// Step 2: Find the largest index `j` such that nums[i] < nums[j]
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
// Step 3: Swap nums[i] and nums[j]
swap(nums[i], nums[j]);
}
// Step 4: Reverse the sequence from nums[i + 1] to the end
reverse(nums.begin() + i + 1, nums.end());
}
};
14.68MB, 4ms
Javascript
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function(nums) {
const n = nums.length;
if (n <= 1) {
return;
}
// Step 1: Find the largest index `i` such that nums[i] < nums[i + 1]
let i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
// Step 2: Find the largest index `j` such that nums[i] < nums[j]
let j = n - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
// Step 3: Swap nums[i] and nums[j]
[nums[i], nums[j]] = [nums[j], nums[i]];
}
// Step 4: Reverse the sequence from nums[i + 1] to the end
reverse(nums, i + 1, n - 1);
};
/**
* Reverses the elements of the array from start to end indices.
* @param {number[]} nums - The array to reverse.
* @param {number} start - The starting index.
* @param {number} end - The ending index.
*/
function reverse(nums, start, end) {
while (start < end) {
[nums[start], nums[end]] = [nums[end], nums[start]];
start++;
end--;
}
}
50.67MB, 70ms
