当前位置:网站首页>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
边栏推荐
- Conversion between hexadecimal numbers
- C语言程序设计之函数的构造
- 386. 字典序排数(中等)-迭代-全排列
- 122. 买卖股票的最佳时机 II-一次遍历
- If you start from zero according to the frame
- JVM class loading mechanism
- Learning record of uni app dark horse yougou project (Part 2)
- 209. Minimum length subarray - sliding window
- Metaprogramming, proxy and reflection
- 索引:手把手教你索引从零基础到精通使用
猜你喜欢
440. The k-th small number of dictionary order (difficult) - dictionary tree - number node - byte skipping high-frequency question
Summary of common SQL statements
Using quartz under. Net core -- job attributes and exceptions of [4] jobs and triggers
2.Electron之HelloWorld
Use of todesk remote control software
2021长城杯WP
958. Complete binary tree test
440. 字典序的第K小数字(困难)-字典树-数节点-字节跳动高频题
索引:手把手教你索引从零基础到精通使用
102. 二叉树的层序遍历
随机推荐
How to manually implement the mechanism of triggering garbage collection in node
给 el-dialog 增加拖拽功能
ECMAScript history
剑指 Offer 03. 数组中重复的数字
C语言函数详解
122. The best time to buy and sell stocks II - one-time traversal
Conversion between hexadecimal numbers
ASP. Net core configuration options (Part 2)
.Net Core3. 1 use razorengine NETCORE production entity generator (MVC web version)
Using quartz under. Net core -- job attributes and exceptions of [4] jobs and triggers
MySQL进阶之索引【分类,性能分析,使用,设计原则】
Qt 修改UI没有生效
STM32 entry development board choose wildfire or punctual atom?
ASP. NET CORE3. 1. Solution to login failure after identity registers users
C语言程序设计之函数的构造
Using quartz under. Net core -- preliminary understanding of [2] operations and triggers
QT modification UI does not take effect
Self use learning notes - connected and non connected access to database
Node template engine (EJS, art template)
Summary of common SQL statements