题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,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]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
原题：LeetCode31. 下一个排列
思路及实现
方式一：双指针法
思路
- 从右向左找到第一个相邻的升序对
(i, i+1)，即nums[i] < nums[i+1]。此时i左侧的元素（如果存在）必然降序排列。 - 如果找不到这样的升序对，说明整个数组是降序排列的，也就是最大的排列，那么直接翻转整个数组即可得到最小排列。
- 如果找到了升序对
(i, i+1)，则从右向左找到第一个大于nums[i]的元素nums[j]。 - 交换
nums[i]和nums[j]。 - 将
i+1及其右边的所有元素反转，使其变为升序排列。
代码实现
Java版本
public class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n - 2;
// 从右向左找到第一个升序对 (i, i+1)
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = n - 1;
// 从右向左找到第一个大于 nums[i] 的元素 nums[j]
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
// 交换 nums[i] 和 nums[j]
swap(nums, i, j);
}
// 反转 i+1 及其右边的所有元素
reverse(nums, i + 1, n - 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}
说明：Java代码使用双指针法实现了寻找下一个排列的逻辑。首先通过
i找到第一个需要变动的位置，然后通过j找到比nums[i]大的元素进行交换，最后反转i之后的元素得到下一个排列。
C语言版本
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void reverse(int* nums, int start, int end) {
while (start < end) {
swap(&nums[start], &nums[end]);
start++;
end--;
}
}
void nextPermutation(int* nums, int numsSize) {
int i = numsSize - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = numsSize - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(&nums[i], &nums[j]);
}
reverse(nums, i + 1, numsSize - 1);
}
说明：C语言版本的实现和Java版本类似，只是用指针操作数组，并且去掉了类和方法的概念。
Python3版本
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j =len(nums) - 1
while j >= 0 and nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
说明：Python版本实现同样使用双指针法，通过索引直接操作列表。在Python中，交换两个变量的值不需要临时变量，直接赋值即可。
Go语言版本
func nextPermutation(nums []int) {
n := len(nums)
i := n - 2
for i >= 0 && nums[i] >= nums[i+1] {
i--
}
if i >= 0 {
j := n - 1
for j >= 0 && nums[j] <= nums[i] {
j--
}
nums[i], nums[j] = nums[j], nums[i]
}
reverse(nums[i+1:])
}
func reverse(nums []int) {
i, j := 0, len(nums)-1
for i < j {
nums[i], nums[j] = nums[j], nums[i]
i++
j--
}
}
说明：Go语言版本的实现也遵循双指针法的思路。Go语言中没有内置的swap函数，所以需要手动实现。reverse函数使用切片来反转数组的一部分。
复杂度分析
- 时间复杂度：O(n)，其中n是数组的长度。整个过程中，最多只遍历了数组两次（寻找i和j，以及反转操作），因此时间复杂度是线性的。
- 空间复杂度：O(1)。除了使用几个临时变量外，没有使用额外的空间。
方式二：使用库函数
思路
可以利用语言内置的排序函数对数组进行部分排序，以找到下一个排列。但这种方式并非题目要求的“原数组操作且只使用额外常量空间”，因此这里只作为一种扩展思路。
代码实现
方式二：使用库函数（非标准解法，违反了题目要求的只使用额外常量空间）
Java版本
import java.util.Arrays;
import java.util.Collections;
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 找到需要改变的位置
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// 如果整个数组是降序排列，则直接反转整个数组
if (i < 0) {
reverse(nums, 0, nums.length - 1);
return;
}
// 找到比nums[i]大的最小元素，并交换
int j = nums.length - 1;
while (nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
// 对i之后的元素进行升序排序
Arrays.sort(nums, i + 1, nums.length);
}
// 反转数组指定范围的元素
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
// 交换数组中两个位置上的元素
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
C++版本
#include <vector>
#include <algorithm>
using namespace std;
void nextPermutation(vector<int>& nums) {
int i = nums.size() - 2;
// 找到需要改变的位置
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// 如果整个数组是降序排列，则直接反转整个数组
if (i < 0) {
reverse(nums.begin(), nums.end());
return;
}
// 找到比nums[i]大的最小元素，并交换
int j = nums.size() - 1;
while (nums[j] <= nums[i]) {
j--;
}
swap(nums[i], nums[j]);
// 对i之后的元素进行升序排序
sort(nums.begin() + i + 1, nums.end());
}
Go版本
import (
"sort"
)
func nextPermutation(nums []int) {
i := len(nums) - 2
// 找到需要改变的位置
for i >= 0 && nums[i] >= nums[i+1] {
i--
}
// 如果整个数组是降序排列，则直接反转整个数组
if i < 0 {
reverse(nums)
return
}
// 找到比nums[i]大的最小元素，并交换
j := len(nums) - 1
for nums[j] <= nums[i] {
j--
}
nums[i], nums[j] = nums[j], nums[i]
// 对i之后的元素进行升序排序
sort.Ints(nums[i+1:])
}
// 反转数组
func reverse(nums []int) {
for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
nums[i], nums[j] = nums[j], nums[i]
}
}
注意事项
这些使用库函数的
Python3版本（非标准解法）
from typing import List
import itertools
def nextPermutation(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 找到需要改变的位置
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
# 如果整个数组是降序排列，则直接反转整个数组
if i < 0:
nums.reverse()
return
# 找到比nums[i]大的最小元素，并交换
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
# 对i之后的元素进行升序排序
nums[i+1:] = sorted(nums[i+1:])
说明：Python版本使用了内置的
sorted函数对数组部分进行排序，这违反了题目要求的“只使用额外常量空间”。因此，这种解法只作为扩展思路，并非标准解法。
复杂度分析
- 时间复杂度：O(n log n)，其中n是数组的长度。主要的时间消耗在排序操作上。
- 空间复杂度：O(n)，因为排序操作可能需要额外的空间来存储排序结果。
总结
| 方式 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 方式一 | 原数组操作，只使用额外常量空间 | 代码实现相对复杂 | O(n) | O(1) |
| 方式二 | 代码简洁，利用了内置函数 | 违反了题目要求的原数组操作和常量空间限制 | O(n log n) | O(n) |
相似题目
| 相似题目 | 难度 | 链接 |
|---|---|---|
| LeetCode 33 | 中等 | 力扣-33 |
| LeetCode 34 | 中等 | [ |
