Next Permutation&&Permutation Sequence
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
题目的意思是:123的全排列按字典顺序为:
123 132 213 231 312 321
如果输入其中某一个序列,返回它的下一个序列。如:输入:213 输出:231 ;输入:321 输出:123
算法思想:举例如下
输入:1 4 6 5 3 2
step1:从右往左找到第一个破坏升序(非严格)的元素,此例中为4.记下标为 i
step2: 依然从右往左,找到第一个大于4的元素,此例中5,交换4和5.
step3:从i+1到最右端,逆置。6 4 3 2 to 2 3 4 6
so,1 5 2 3 4 6 即为所求。
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i,j,len=nums.size();
for(i=len-;i>=;--i)
{
if(nums[i+]>nums[i])
{
for(j=len-;j>i-;--j)if(nums[j]>nums[i])break;
swap(nums[i],nums[j]);
reverse(nums.begin()+i+,nums.end());
return;
}
}
reverse(nums.begin(),nums.end());
return; }
};
Permutation Sequence
The set [1,2,3,…,n]
contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
解法参考了:http://blog.csdn.net/lanxu_yy/article/details/17261527
思路:
思路1是用NP的方式来罗列出所有的排列再找出第k个结果,这种方法的时间复杂度与空间复杂度比较高。思路2是研究排序结果的规律,例如取n是,结果可以分为n个组,第一组是第一个数字取最小的那个(即1),第k组是取数字排第k小的那个(即k),每组的数字个数是(n-1)!。依次类推可以递归到n为1时。最终k可以表示为k=A1(n-1)!+A2(n-2)!+...+An,其中Ak代表该数为剩余数字中第Ak小的数字。
class Solution {
public:
string getPermutation(int n, int k) {
vector<bool> flag(n,false);
int *A=new int[n];
int base=;
for(int i=;i<n;i++)
base*=i;
int sum=k-;
for(int i=;i<n;i++)
{
A[i]=sum/base;
sum=sum%base;
if(base!=)
base=base/(n--i);
}
string str;
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{
if(!flag[j])
{
if(A[i]==)
{
str.push_back(j+'');
flag[j]=true;
break;
}
else
{
A[i]--;
}
}
}
return str;
}
};
最新文章
- http://blog.csdn.net/shawnkong/article/details/52045894
- 【代码笔记】iOS-饼图
- jquery循环延迟加载,用于在图片加载完成后再加载js
- 李洪强iOS开发之静态库
- POJ_3068_Shortest_pair_of_paths_(最小费用流)
- partial局部类
- dnsever 邮件记录
- node中的Readable - flowing/non-flowing mode
- linux+nginx+mysql+php高性能服务器搭建
- apache 提示You don&#39;t have permission to access /test.php on this server.怎样解决
- exit()与_exit()的区别(转)
- 图形绘制中的PorterDuffXfermode
- Java内部抽象类的匿名类初始化
- LeetCode 字符串专题(一)
- Python 元组tuple相关知识
- 10)django-ORM(创建,字段类型,字段参数)
- 3-Python3从入门到实战—基础之数据类型(数字-Number)
- day13 生成器 三元运算 列表解析
- shell脚本返回字符串
- java 封装02