LeetCode-31 下一个排列
> 题目：31. 下一个排列
> 难度：中等
> 分类：数组
> 解决方案：数组遍历
今天我们学习第31题下一个排列，这是一个中等的数组题。我们先看看这道题的题目描述。
题目描述
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1分析
这是一个数组排列的题，首先我们需要弄明白什么是数组的下一个排列。我们可以对数字1、2和3这三个数形成的数组进行排列，如下图所示：
对具体排列方法分析如下图所示：
上述分析所对应的 java代码如下所示：
class Solution { public void nextPermutation(int[] nums) { // 从右向左遍历，存储第一个下降的数的坐标 int i = 0; // 从右向左遍历，存储第一个大于nums[i]的数的坐标 int j = 0;
if(nums == null || nums.length < 2) return ;
// 从右向左找到第一个降序的数，坐标为i for(int k=nums.length -2; k>=0; k--){ if(nums[k] < nums[k+1]){ i = k; break; } }
// 从右向左找到第一个大于nums[i]的数，坐标为j for(int k=nums.length-1; k>=0; k--){ if(nums[k] > nums[i]){ j = k; break; } }
// 交换 nums[i] 和 nums[j] swap(nums, i, j);
// 转置从i+1(0)到nums.length-1的数 int n = 0; if(i == 0 && j == 0) n = 0; else n = i + 1; int m = nums.length-1; while(n < m){ swap(nums, n, m); ++n; --m; } }
// 数组中两个数字交换函数 private void swap(int[] nums, int i, int j){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }}
Github地址
LeetCode-31 下一个排列：https://github.com/JacobLei/leetcode/blob/master/src/main/java/A28_ImplementstrStr.java
参考链接
下一个排列：https://leetcode-cn.com/problems/next-permutation/
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-06-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录