当前位置:网站首页>31. Next arrangement
31. Next arrangement
2022-04-23 17:39:00 【hequnwang10】
One 、 Title Description
An integer array array Is to arrange all its members in sequence or linear order .
- for example ,arr = [1,2,3] , The following can be regarded as arr Permutation :[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] .
Integer array Next spread It refers to the next lexicographic order of its integers . More formally , Arrange all the containers in the order from small to large , So the array of Next spread It is the arrangement behind it in this ordered container . If there is no next larger arrangement , Then the array must be rearranged to the lowest order in the dictionary ( namely , Its elements are arranged in ascending order ).
- for example ,arr = [1,2,3] The next line up for is [1,3,2] .
- Similarly ,arr = [2,3,1] The next line up for is [3,1,2] .
- and arr = [3,2,1] The next line up for is [1,2,3] , because [3,2,1] There is no greater order of dictionaries .
Give you an array of integers nums , find nums The next permutation of .
must In situ modify , Only additional constant spaces are allowed .
Example 1:
Input :nums = [1,2,3]
Output :[1,3,2]
Example 2:
Input :nums = [3,2,1]
Output :[1,2,3]
Example 3:
Input :nums = [1,1,5]
Output :[1,5,1]
Two 、 Problem solving
Two traversal
class Solution {
public void nextPermutation(int[] nums) {
// You need to find the first ascending subscript from the back
int length = nums.length;
int end = length-2;
// If the current value is greater than the following value , Keep looking for , Always find the first ascending subscript
while(end >= 0 && nums[end] >= nums[end+1]){
end--;
}
// After finding the subscript value , Find a value greater than the subscript value after
// Pay attention to the boundary conditions
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://yzsam.com/2022/04/202204231732009984.html
边栏推荐
- Shell-sed命令的使用
- Advantages and disadvantages of several note taking software
- 超分之TDAN
- [related to zhengheyuan cutting tools]
- [二叉数] 二叉树的最大深度+N叉树的最大深度
- 基于51单片机红外无线通讯仿真
- [WPF binding 3] listview basic binding and data template binding
- 198. 打家劫舍-动态规划
- ClickHouse-数据类型
- In ancient Egypt and Greece, what base system was used in mathematics
猜你喜欢
958. Complete binary tree test
MySQL进阶学习之SQL优化【插入,主键,排序,分组,分页,计数】
Compare the performance of query based on the number of paging data that meet the query conditions
Qt 修改UI没有生效
Deep understanding of control inversion and dependency injection
440. 字典序的第K小数字(困难)-字典树-数节点-字节跳动高频题
Signalr can actively send data from the server to the client
Collection of common SQL statements
嵌入式系统中,FLASH中的程序代码必须搬到RAM中运行吗?
[logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
随机推荐
Shell-cut命令的使用
STM32 entry development board choose wildfire or punctual atom?
常用SQL语句总结
SiteServer CMS5. 0 Usage Summary
ASP. NET CORE3. 1. Solution to login failure after identity registers users
Understanding of RPC core concepts
ros常用的函数——ros::ok(),ros::Rate,ros::spin()和ros::spinOnce()
stm32入门开发板选野火还是正点原子呢?
Use of five routing guards
Simulation of infrared wireless communication based on 51 single chip microcomputer
Self use learning notes - connected and non connected access to database
01-初识sketch-sketch优势
Websocket (basic)
If you start from zero according to the frame
470. Rand10() is implemented with rand7()
flink 学习(十二)Allowed Lateness和 Side Output
198. 打家劫舍-动态规划
Collection of common SQL statements
Compare the performance of query based on the number of paging data that meet the query conditions
MySQL进阶之索引【分类,性能分析,使用,设计原则】