JAVA练习326- 下一个排列

题目概览

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

• 例如，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

来源：31. 下一个排列 - 力扣（LeetCode）

解题分析

方法：两次遍历

以 [ 1,2,3,6,5,4 ] 为例，他的下一个排列是 [ 1,2,4,3,5,6 ]，可以看出一个排列中至少存在一个升序排列，一个降序排列，我们把共同的元素算给降序排列，那么下一个排列就是将 最右侧升序排列中的最大值（令此时索引为 i）与 最右侧的降序排列中的较小值（令此时索引为 j，nums[ j ] 一定要大于 nums[ i ] 且 nums [ j ] 最小）进行交换 ，然后将 i 后面的排列调整为升序（原本已经为降序，反转即可）。

具体实现：

1. 从右侧开始遍历，找到第一个相邻且满足 nums[ i ] < nums[ j ] 的位置，此时 [ i, j ] 就为右侧第一个升序排列，[ j, n-1 ] 就为右侧第一个降序排列，i 就是升序排列中的最大值。
2. 从右侧开测遍历，找到第一个满足 num[ i ] < nums[ k ] 的位置，k 就是降序排列中较小值。
3. 交换 i 和 k，反转 [ i + 1, n-1 ]。

时间复杂度：O(n)
空间复杂度：O(1)

class Solution { public void nextPermutation(int[] nums) { int n = nums.length; if (n == 1) { return; } int i = n - 2, j = n - 1; while(i >= 0 && nums[i] >= nums[j]) { i--; j--; } if (i < 0) { for (int z = 0; z < n / 2; ++z) { swap(nums, z, n - 1 - z); } return; } int k = n - 1; while(nums[i] >= nums[k]) { k--; } swap(nums, i, k); int l = n - 1; for (int z = i + 1; z <= (n + i) / 2; ++z) { swap(nums, z, l--); } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }