当前位置:网站首页>leetcode-31:下一个排列
leetcode-31:下一个排列
2022-07-05 05:46:00 【菊头蝙蝠】
题目
题目连接
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如,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]
解题
方法一:
- 以12385764为例子,由于要查找下一个更大的,因此要倒序遍历。
- 倒序遍历,找到第一个递增的相邻元素57 (因此后面的元素一定是递减的,764)
- 然而并不能直接让5和7进行交换,而是让5和6交换。因此倒序遍历到找第一个比5大的元素,是6
- 交换完后变成了12386754,然而这并不是想要的下一个更大的元素(而是下面好几个元素)。因此对后面部分进行排序 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());
}
};
边栏推荐
- Sword finger offer 05 Replace spaces
- 全排列的代码 (递归写法)
- Brief introduction to tcp/ip protocol stack
- 游戏商城毕业设计
- 使用Electron开发桌面应用
- 884. Uncommon words in two sentences
- Time of process
- Implement a fixed capacity stack
- Maximum number of "balloons"
- [practical skills] technical management of managers with non-technical background
猜你喜欢
用STM32点个灯
Some common problems in the assessment of network engineers: WLAN, BGP, switch
shared_ Repeated release heap object of PTR hidden danger
Smart construction site "hydropower energy consumption online monitoring system"
F - Two Exam(AtCoder Beginner Contest 238)
剑指 Offer 04. 二维数组中的查找
Graduation project of game mall
剑指 Offer 05. 替换空格
YOLOv5-Shufflenetv2
LeetCode 0108.将有序数组转换为二叉搜索树 - 数组中值为根,中值左右分别为左右子树
随机推荐
EOJ 2021.10 E. XOR tree
智慧工地“水电能耗在线监测系统”
Sword finger offer 35 Replication of complex linked list
从Dijkstra的图灵奖演讲论科技创业者特点
数仓项目的集群脚本
Reflection summary of Haut OJ freshmen on Wednesday
用STM32点个灯
Daily question - Search two-dimensional matrix PS two-dimensional array search
Dynamic planning solution ideas and summary (30000 words)
Smart construction site "hydropower energy consumption online monitoring system"
二十六、文件系统API(设备在应用间的共享;目录和文件API)
After setting up the database and website When you open the app for testing, it shows that the server is being maintained
Little known skills of Task Manager
Chapter 6 data flow modeling - after class exercises
Animation scoring data analysis and visualization and it industry recruitment data analysis and visualization
CF1634E Fair Share
Individual game 12
Daily question 1688 Number of matches in the competition
CCPC Weihai 2021m eight hundred and ten thousand nine hundred and seventy-five
个人开发的渗透测试工具Satania v1.2更新