当前位置:网站首页>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());
}
};
边栏推荐
- API related to TCP connection
- CPU内核和逻辑处理器的区别
- 【Rust 笔记】13-迭代器(中)
- F - Two Exam(AtCoder Beginner Contest 238)
- Overview of variable resistors - structure, operation and different applications
- LVS简介【暂未完成(半成品)】
- Spark中groupByKey() 和 reduceByKey() 和combineByKey()
- Erreur de connexion Navicat à la base de données Oracle Ora - 28547 ou Ora - 03135
- leetcode-31:下一个排列
- Implement a fixed capacity stack
猜你喜欢
【Jailhouse 文章】Performance measurements for hypervisors on embedded ARM processors
Educational Codeforces Round 116 (Rated for Div. 2) E. Arena
Overview of variable resistors - structure, operation and different applications
Appium自动化测试基础 — Appium测试环境搭建总结
SQLMAP使用教程(一)
[practical skills] how to do a good job in technical training?
Analysis of backdoor vulnerability in remote code execution penetration test / / phpstudy of national game title of national secondary vocational network security B module
Wazuh開源主機安全解决方案的簡介與使用體驗
Full Permutation Code (recursive writing)
Sqlmap tutorial (II) practical skills I
随机推荐
One question per day 2047 Number of valid words in the sentence
leetcode-1200:最小绝对差
The connection and solution between the shortest Hamilton path and the traveling salesman problem
Dichotomy, discretization, etc
One question per day 1765 The highest point in the map
Smart construction site "hydropower energy consumption online monitoring system"
7. Processing the input of multidimensional features
Personal developed penetration testing tool Satania v1.2 update
智慧工地“水电能耗在线监测系统”
传统数据库逐渐“难适应”,云原生数据库脱颖而出
liunx启动redis
【Rust 笔记】13-迭代器(中)
Introduction and experience of wazuh open source host security solution
Data visualization chart summary (I)
Implement a fixed capacity stack
【Rust 笔记】15-字符串与文本(下)
2022 极术通讯-Arm 虚拟硬件加速物联网软件开发
Solution to game 10 of the personal field
[jailhouse article] performance measurements for hypervisors on embedded ARM processors
MIT-6874-Deep Learning in the Life Sciences Week 7