Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3
→1,3,2
3,2,1
→1,2,3
1,1,5
→1,5,1
本题关键也是理解题意是什么,然后画图,总结规律。
1 从尾端往前寻找前一个元素比后一个元素小的位置i。找到这个位置之后,继续从后往前找,找到第一个大于num[i]的元素,交换;
2 i元素之后的元素排序,或者转置,都可以随你喜欢。 如果整个序列是倒序的,那么直接转置,或者排序都可以。
不过还有更加简单的LeetCode有史以来最简单的一句话程序,看下面。
2013-12-21 Update:
更新一个程序,我还是喜欢下面这个新写的程序,感觉思路更加清晰:
class Solution {
public:
void nextPermutation(vector<int> &num)
{
int n = num.size();
int i = n-2;
while (i>=0 && num[i] >= num[i+1]) i--;
if (i < 0)
{
reverse(num.begin(), num.end());
return;
}
int k = n-1;
while (num[k] <= num[i]) k--;
swap(num[i], num[k]);
reverse(num.begin()+i+1, num.end());
}
};
程序如下:
void nextPermutation2(vector<int> &num)
{
if (num.size() < 2) return;
for (int i=num.size()-1;;i--)
{
if (i == 0)
{
reverse(num.begin(), num.end());
return;
}
if (num[i-1] < num[i])
{
int k = num.size()-1;
//注意是<=不是<,否则出现如1,5,1这样会结果错误的。
while (num[k] <= num[i-1])
{
k--;
}
swap(num[i-1], num[k]);
reverse(num.begin()+i, num.end());
return;
}
}
}
void nextPermutation3(vector<int> &num)
{
if(num.size()<2) return;
for (int i=num.size()-1;;i--)
{
if (i == 0)
{
reverse(num.begin(), num.end());
return;
}
if (num[i-1] < num[i])
{
int k = num.size()-1;
//注意是<=不是<,否则出现如1,5,1这样会结果错误的。
while (num[k] <= num[i-1])
{
k--;
}
swap(num[i-1], num[k]);
sort(num.begin()+i, num.end());
return;
}
}
}
LeetCode有史以来最简单的一句话程序,调用STL函数库AC的程序:
void nextPermutation(vector<int> &num)
{
next_permutation(num.begin(), num.end());
}
//2014-1-26 update
class Solution126 {
public:
void nextPermutation(vector<int> &num)
{
int idx1 = num.size()-2, idx2 = num.size()-1;
//num[idx1]>=num[idx1+1]一定要写>=,不能是>,举例没举好也会出错。
for ( ; idx1>=0 && num[idx1] >= num[idx1+1]; idx1--);
if (idx1 < 0)
{
reverse(num.begin(), num.end());
return;
}
for ( ; idx2>=0 && num[idx2] <= num[idx1]; idx2--);
swap(num[idx1], num[idx2]);
reverse(num.begin()+idx1+1, num.end());
}
};
分享到:
相关推荐
31.Next_Permutation_下一个排列【LeetCode单题讲解系列】
解题思路序列化:通过深度优先搜索的方式,递归遍历节点,以 root.val、len(root.children)、root.children 的顺序生成序列化结
Source file for LeetCode Permutations Problem
输入leetcode测试用例[1,2,null,3]类型字符串,返回根节点指针。判断逻辑和leetcode一致,null结点无须额外输入null子结点,并且自动舍弃无效结点,例如输入[1,null,2,null,null,...网上找的都是错的,自己就写了一个。
使用Scrapy框架从LeetCode上下载自己的提交记录,并生成一个markdown文件
简介:给定一个未经排序的整数数组,找到最长且连续递增的子序列,并返回该序列的长度。题解 1 - typescript编辑时间:2021.1.24执行用时:92m
LeetCode674. 最长连续递增序列674. 最长连续递增序列解题思路:记录每次递增序列的长度,max存储最大长度// 递增序列更新最大长度} else
序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。 请设计一个算法来实现...
title: "[0946] 验证栈序列"题目描述给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推
给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返
题目位置题解* 思路* 1、记录当前长度和最大长度* 2、每次不符合长度的时候(也就是后面一个数字不大于前面一个数的时候)让就最大长度等于当前长度和最大长度的最
当我们遇到一个非空节点时,我们可以记录下这个节点的值。 如果它是一个空节点,我们可以使用一个标记值记录,例如 #。 _9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \ / \ # # # # # # 例如,上面的二叉树可以被序列...
python leetcode常用函数 Python LeetCode常用函数 LeetCode是一个非常流行的算法题库,许多程序员都会在... sorted()函数可以对一个序列进行排序。在LeetCode中,我们经常需要使用sorted()函数来对数组或者列表进行排
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
自下向上 class Solution(object): # Modify the original triangle, bottom-up def minimumTotal(self, triangle): """ :type triangle: List[List[int]] :rtype: int """ if not triangle: return for i...
1143. 最长公共子序列参考解法解法一:简单的动态规划直接用二位数组。优化二位动态数组用二个数组进行表示继续优化用以为数组进行表示。//代表dp[i - 1]
c++ c++_c++编程基础之leetcode题解第60题排列序列
来源:力扣(LeetCode) 链接::过滤特殊情况,
Leetcode原题Count and Say count-and-say序列是整数序列,前五个术语如下: 1. 1 2. 11 3. 21 1211 5. 111221 1被读作“1”或11。 11被读作“两个1”或21。 21被读作“一个2,然后一个1”或1211。 给定整数n,...