当前位置:网站首页>Leetcode-31: next spread
Leetcode-31: next spread
2022-07-05 06:09:00 【Chrysanthemum headed bat】
leetcode-31: Next spread
subject
Topic linking
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]
Problem solving
Method 1 :
- With 12385764 As an example , Because you want to find the next bigger , So we need to traverse in reverse order .
- Reverse traversal , Find the first incremental adjacent element 57 ( Therefore, the following elements must be decreasing ,764)
- However, we cannot directly let 5 and 7 swapping , Rather let 5 and 6 In exchange for . So we can traverse in reverse order to find the first ratio 5 Big elements , yes 6
- After the exchange, it became 12386754, However, this is not the next larger element you want ( But there are several elements below ). So sort the latter part 12386 754---->12386 457
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n=nums.size();
int i=n-2,j=n-1;
while(i>=0&&nums[i]>=nums[j]){
i--;
j--;
}
int k=n-1;
if(i>=0){
while(nums[i]>=nums[k]) k--;
swap(nums[i],nums[k]);
}
sort(nums.begin()+i+1,nums.end());
}
};
边栏推荐
- CPU内核和逻辑处理器的区别
- 【Rust 笔记】13-迭代器(中)
- SQLMAP使用教程(二)实战技巧一
- 中职网络安全技能竞赛——广西区赛中间件渗透测试教程文章
- Educational Codeforces Round 116 (Rated for Div. 2) E. Arena
- 1.13 - RISC/CISC
- Overview of variable resistors - structure, operation and different applications
- Collection: programming related websites and books
- Navicat连接Oracle数据库报错ORA-28547或ORA-03135
- Arduino 控制的 RGB LED 无限镜
猜你喜欢
随机推荐
1039 Course List for Student
Flutter Web 硬件键盘监听
【Rust 笔记】13-迭代器(下)
Appium automation test foundation - Summary of appium test environment construction
1041 Be Unique
Wazuh開源主機安全解决方案的簡介與使用體驗
Codeforces Round #732 (Div. 2) D. AquaMoon and Chess
R语言【数据集的导入导出】
Convolution neural network -- convolution layer
2022年貴州省職業院校技能大賽中職組網絡安全賽項規程
Arduino 控制的 RGB LED 无限镜
1040 Longest Symmetric String
做 SQL 性能优化真是让人干瞪眼
Sqlmap tutorial (1)
Control unit
Appium自动化测试基础 — Appium测试环境搭建总结
Introduction to convolutional neural network
Simply sort out the types of sockets
liunx启动redis
“磐云杯”中职网络安全技能大赛A模块新题