LeetCode31. 下排列
1)题目
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如,
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
2)思路
思路:只有一个数,直接返回;
倒数第二个数小于最后一个数,比如[1,3],直接交换位置返回;
[1,2,3] => [1,3,2]
[2,1,3] => [2,3,1]
其他情况进行处理:
[2,3,1] => [3,1,2]
[1,3,2] => [2,1,3]
发现规律:
移动到不是倒序排序的值时,取该值与倒序排序部分进行比较,取恰好比该值大一点的值放到该位置上,
剩余倒序部分的值和值一起进行正序排序,然后接到该位置的后面。
例:[2,3,1] => [3,1,2]
3>2时,2与倒序部分进行比较[3,1](先取最小值比较,没有比该数大时,使用第二小的值比较,直到刚好比该值大),
取到3,把这个值3提到2的位置上nums[0] = 3,剩余倒序部分的值[1]和2一起进行正序排序,然后接到该位置的后面。
最后得到结果[3,1,2]
没有发现有前一个数比后一个数小的情况,那直接反过来赋值输出就好了。
[3,2,1] => [1,2,3]
3)代码
public static void nextPermutation(int[] nums) {
int length = nums.length;
if (length < 2) return;
if (nums[length-1]>nums[length-2] || length == 2) {
// 交换位置
int value = nums[length - 1];
nums[length - 1] = nums[length - 2];
nums[length - 2] = value;
return;
}
List<Integer> list = new ArrayList<>();
int i = length - 1;
while (i >= 0) {
list.add(nums[i]);
if (i > 0 && nums[i] > nums[i - 1]) {
for (int j = 0; j < list.size(); j ) {
int minValue = list.get(j);
if (minValue > nums[i - 1]) {
list.remove(list.get(j));
list.add(nums[i - 1]);
Collections.sort(list);
nums[i - 1] = minValue;
break;
}
}
i--;
break;
}
i--;
}
for (int k = 0; k < list.size(); k ) {
nums[ i] = list.get(k);
}
}
4)结果
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhieeehe
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
excel图片置于文字下方的方法
PHP中文网 06-27 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
微信提示登录环境异常是什么意思原因
PHP中文网 04-09 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22 -
微信人名旁边有个图标有什么用
PHP中文网 03-11