当前位置:网站首页>31. 下一个排列
31. 下一个排列
2022-04-23 17:32:00 【hequnwang10】
一、题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如,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]
二、解题
两次遍历
class Solution {
public void nextPermutation(int[] nums) {
//需要从后面找到第一个升序下标
int length = nums.length;
int end = length-2;
//如果当前值大于后面的那个值,继续往前找,一直找到第一个升序的下标
while(end >= 0 && nums[end] >= nums[end+1]){
end--;
}
//找到下标值后,在找到后面大于下标值的值
//注意边界条件
if(end >= 0){
int next = length - 1;
while(next >= 0 && nums[end] >= nums[next]){
next--;
}
swap(nums,end,next);
}
reverse(nums,end+1);
}
public void swap(int[] nums,int left,int right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
public void reverse(int[] nums,int left){
int right = nums.length-1;
while(left <= right){
swap(nums,left,right);
left++;
right--;
}
}
}
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hequnwang10/article/details/124209001
边栏推荐
- 基于51单片机红外无线通讯仿真
- node中,如何手动实现触发垃圾回收机制
- Model problems of stock in and stock out and inventory system
- 【WPF绑定3】 ListView基础绑定和数据模板绑定
- How to sort the numbers with text in Excel from small to large instead of the first number
- Some problems encountered in recent programming 2021 / 9 / 8
- Clickhouse SQL operation
- C# Task. Delay and thread The difference between sleep
- MySQL installation
- Detailed explanation of C webpai route
猜你喜欢
Using quartz under. Net core -- general properties and priority of triggers for [5] jobs and triggers
01 - get to know the advantages of sketch sketch
Webapi + form form upload file
XTask与Kotlin Coroutine的使用对比
EF core in ASP Generate core priority database based on net entity model
Using quartz under. Net core -- job attributes and exceptions of [4] jobs and triggers
Simulation of infrared wireless communication based on 51 single chip microcomputer
JVM类加载机制
Halo 开源项目学习(二):实体类与数据表
[difference between Oracle and MySQL]
随机推荐
Collection of common SQL statements
Why do some people say SCM is simple and I have to learn it so hard?
Use between nodejs modules
Shell-入门、变量、以及基本的语法
QT modification UI does not take effect
给 el-dialog 增加拖拽功能
Understanding and small examples of unity3d object pool
Change Oracle to MySQL
440. 字典序的第K小数字(困难)-字典树-数节点-字节跳动高频题
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
How to sort the numbers with text in Excel from small to large instead of the first number
ASP. Net core configuration options (Part 2)
[related to zhengheyuan cutting tools]
[logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
Generation of barcode and QR code
JS failed to change all variables and changed to the return method. Finally, the problem was solved
Clickhouse SQL operation
Using quartz under. Net core -- preliminary understanding of [2] operations and triggers
El date picker limits the selection range from the current time to two months ago
剑指 Offer 22. 链表中倒数第k个节点-快慢指针