【LeetCode 题解】算法：31.下一个排列

一、题目描述​

给定一个整数数组nums，找出它在字典序中更大的下一个排列。如果不存在更大的排列，就将数组重排为字典序最小的排列。并且要求在原数组上进行修改，不使用额外的大量空间。​

二、解题思路​

（一）排列规律分析​

以[1, 2, 3]为例，其按字典序从小到大的排列依次为[1, 2, 3]、[1, 3, 2]、[2, 1, 3]、[2, 3, 1]、[3, 1, 2]、[3, 2, 1]。通过分析这些排列，可以总结出寻找下一个排列的步骤：​

• 从右向左扫描：从数组的最右端开始，找到第一个nums[i] < nums[i + 1]的位置。这表明nums[i]右侧的元素呈降序排列。​

• 确定替换元素：如果找到了符合条件的i，就在nums[i + 1]到数组末尾的范围内，找到一个最小的nums[j]，且满足nums[j] > nums[i]。​

• 交换元素：将nums[i]和nums[j]进行交换。​

• 反转右侧：对nums[i + 1]到数组末尾的元素进行反转，因为此时这部分元素是降序的，反转后变为升序，可得到最小的排列。​

（二）Java 代码实现​

​

class Solution {​

public void nextPermutation(int[] nums) {​

int i = nums.length - 2;​

while (i >= 0 && nums[i] >= nums[i + 1]) {​

i--;​

}​

if (i >= 0) {​

int j = nums.length - 1;​

while (nums[j] <= nums[i]) {​

j--;​

}​

swap(nums, i, j);​

}​

reverse(nums, i + 1, nums.length - 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--;​

}​

}​

}​

​

可以在测试类中这样验证：​

public class Main {​

public static void main(String[] args) {​

int[] nums = {1, 2, 3};​

Solution solution = new Solution();​

solution.nextPermutation(nums);​

for (int num : nums) {​

System.out.print(num + " ");​

}​

}​

}​

​

三、复杂度分析​

1. 时间复杂度：最坏情况下，我们需要扫描数组两次，一次寻找i，另一次寻找j。因此，时间复杂度为​O(n)，其中n是数组的长度。​

2. 空间复杂度：代码仅使用了常数级别的额外空间，因此空间复杂度为​O(1)。

感谢各位的阅读，后续将持续给大家讲解力扣中的算法题和数据库题，如果觉得这篇内容对你有帮助，别忘了点赞和关注，后续还有更多精彩的算法解析与你分享！