LeetCode:下一个排列【31】
2024-09-06 20:01:37
LeetCode:下一个排列【31】
题目描述
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。1,2,3
→ 1,3,2
3,2,1
→ 1,2,3
1,1,5
→ 1,5,1
题目分析
什么样的排列将产生下一个更大的数字呢?
观察上面这个图,我们需要将数字 a[i-1]替换为位于其右侧区域的数字中比它更大的数字,例如 a[j]。我们交换数字 a[i-1]和 a[j]。我们现在在索引 i-1处有正确的数字。
但目前的排列仍然不是我们正在寻找的排列。我们需要通过仅使用 a[i-1]右边的数字来形成最小的排列。因此,我们需要放置那些按升序排列的数字,以获得最小的排列。
具体的操作如下:
Java题解
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length-2;
while(i>=0&&nums[i+1]<=nums[i])
i--;
if(i>=0)
{
int j = nums.length-1;
while(j>=0&&nums[j]<=nums[i])
j--;
swap(nums,i,j);
}
reverse(nums,i+1); } private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
} private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
最新文章
- css display:inline-block 出现空格解决方案
- 《Wireshark数据包分析实战》 - http背后,tcp/ip抓包分析
- OkHttp使用进阶 译自OkHttp Github官方教程
- Spark Programming--Transformations
- MFC VC6++学习笔记
- 卸载RedHat7自带的yum,安装并使用网易163源
- LeetCode 229. Majority Element II (众数之二)
- 让Myeclipse自动生成的get set方法 自动加上文本注释,并且注释内容包含字段中我们加的文档注释
- 【转载】SpringCloud-Eurek 心跳阈值说明
- php源码学习——开篇
- Unity之AssetBundle打包
- msp430学习笔记-ADC12
- Tyvj1038 忠诚 (线段树)
- HDU 4920 Matrix multiplication(矩阵相乘)
- 27. Green Building 绿色建筑
- 动态链接库编程:非MFC DLL
- 在myeclipse的工作环境上配置默认编码为UTF-8
- BZOJ 2049: [Sdoi2008]Cave 洞穴勘测——LCT
- window_onload和body_onload
- 将服务器上的SqlServer数据库备份到本地
热门文章
- 237. Delete Node in a Linked List【easy】
- pthread_cleanup_push和pthread_cleanup_pop清除函数是否执行的说明
- java继承机制
- hive分桶 与保存数据的方式
- Swoole系列(三):建立TCP服务器并发送数据测试
- Java NIO(1):迟迟登场的NIO
- tcp/iP协议族——IP工作原理及实例具体解释(下)
- php文件加密
- spark+hadoop+sqoop+hive平台bug解决方法
- 解决ios8 webView加载的地图无法定位问题