Leetcode31--->Next Permutation(数字的下一个排列)
2024-08-26 21:45:57
题目: 给定一个整数,存放在数组中,求出该整数的下一个排列(字典顺序);要求原地置换,且不能分配额外的内存
举例:
1,2,3
→ 1,3,2;
3,2,1
→ 1,2,3;
1,1,5
→ 1,5,1;
解题思路:
1. 由于要找出整数的下一个排列,且按照字典顺序,因此要找出当前排列中需要交换的的那个位,即找到从右到左第一个不满足升序的元素的前一个元素nums[index1], 以及从右到左第一个大于nums[index1]的元素nums[index2];
2. 交换两个元素;因为是按字典顺序排列的,而nums[index2]是第一个大于nums[index1]的元素,此时[index1 + 1, index2]之间的元素都是大于nums[index2]以及nums[index1]的,而nums[index2]是从右往左第一个大于nums[index1]的元素,因此[index2 + 1, len]的元素都是小于nums[index1],因此当nums[index1]与nums[index2]交换后,[index1 + 1, len]之间的元素就是一个降序
3. 但是由于在交换了nums[index1]和nums[index2]元素后,nums[index2]元素后面本应该是按字典顺序最小的数字组合,而[index1 + 1,结尾]之间的元素是降序的,是字典顺序的最大组合排列,因此需要将[index1 + 1, 结尾]之间的数据全部逆转,才能得到字典的下一个排列组合;
代码如下:
public class Solution {
public void nextPermutation(int[] nums) {
if(nums == null || nums.length < 1)
return;
int len = nums.length - 1;
int data = nums[len];
int index1 = -1;
int index2 = 0;
for(int i = len - 1; i >= 0; i--) // 找到从右往左第一个不满足升序的元素的前一个元素
{
if(data <= nums[i])
data = nums[i];
else
{
index1 = i;
break;
}
}
if(index1 != -1) // 表示可以找到这样的数,即给定的数字不是降序
{
for(int i = len; i >=0; i--) // 找到从右往左第一个大于第一次找到的那个元素的元素
{
if(nums[i] > nums[index1])
{
index2 = i;
break;
}
}
exchange(nums, index1, index2); //此时[index1 + 1, index2]之间的元素都是大于nums[index2]以及nums[index1]的,而nums[index2]是从右往左第一个大于nums[index1]的元素,因此[index2 + 1, len]的元素都是小于nums[index1],
因此当nums[index1]与nums[index2]交换后,[index1 + 1, len]之间的元素就是一个降序 }
index1 = index1 + 1;
while(index1 < len) // 将index1位置之后的元素全部逆转【index + 1, len】之间的元素是降序排列,而我们需要的是nums[index1]元素之后的最小排列组合
{
exchange(nums, index1, len);
index1 ++;
len --;
}
}
public void exchange(int[] nums, int index1, int index2)
{
int data = nums[index1];
nums[index1] = nums[index2];
nums[index2] = data;
}
}
最新文章
- 微软Team Foundation Service 的Scrum模板中的Feature和Backlog Items 的区别【转载】
- ACM/ICPC 之 昂贵的聘礼-最短路解法(POJ1062)
- BZOJ 1029 &; 丝帛贪心
- MySQL远程访问授权
- HTTP协议中TCP的三次握手,四次挥手总结
- JS瀑布流布局模式(1)
- GDB 入门篇
- 学习tcl的资源
- Tomcat根目录下work文件夹的作用
- 北京哪儿有卖tods豆豆鞋的?在线等答案、、、、(类似动物园、西单等地)_百度知道
- IP分类以及特殊IP
- 蚂蚁金服新一代数据可视化引擎 G2
- Webstorm 2017.3激活破解
- 限制输入字数JS
- Spring生命周期 Constructor >; @PostConstruct >; InitializingBean >; init-method
- ansible 使用记录
- 使用pip cmd安装包
- Ubuntu 16.04配置JDK
- C#编程(五十五)----------HashSet和SortedSet
- Qt5布局管理(三)——QStackedWidget堆栈窗口类