题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。例如，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版本
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) - 2while i >= 0 and nums[i] >= nums[i + 1]:i -= 1if i >= 0:j =len(nums) - 1while j >= 0 and nums[j] <= nums[i]:j -= 1nums[i], nums[j] = nums[j], nums[i]left, right = i + 1, len(nums) - 1while left < right:nums[left], nums[right] = nums[right], nums[left]left += 1right -= 1
说明：Python版本实现同样使用双指针法，通过索引直接操作列表。在Python中，交换两个变量的值不需要临时变量，直接赋值即可。
Go语言版本
func nextPermutation(nums []int) {n := len(nums)i := n - 2for i >= 0 && nums[i] >= nums[i+1] {i--}if i >= 0 {j := n - 1for 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)-1for i < j {nums[i], nums[j] = nums[j], nums[i]i++j--}
}
说明：Go语言版本的实现也遵循双指针法的思路。Go语言中没有内置的swap函数，所以需要手动实现。reverse函数使用切片来反转数组的一部分。
复杂度分析
- 时间复杂度：O(n)，其中n是数组的长度。整个过程中，最多只遍历了数组两次（寻找i和j，以及反转操作），因此时间复杂度是线性的。
- 空间复杂度：O(1)。除了使用几个临时变量外，没有使用额外的空间。
方式二：使用库函数
思路
可以利用语言内置的排序函数对数组进行部分排序，以找到下一个排列。但这种方式并非题目要求的“原数组操作且只使用额外常量空间”，因此这里只作为一种扩展思路。
代码实现
方式二：使用库函数（非标准解法，违反了题目要求的只使用额外常量空间）
Java版本
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) - 1for 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 itertoolsdef nextPermutation(nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""# 找到需要改变的位置i = len(nums) - 2while i >= 0 and nums[i] >= nums[i + 1]:i -= 1# 如果整个数组是降序排列，则直接反转整个数组if i < 0:nums.reverse()return# 找到比nums[i]大的最小元素，并交换j = len(nums) - 1while nums[j] <= nums[i]:j -= 1nums[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 | 中等 | [ |
