返回信息流近期在刷leetcode,然后碰到了关于全排列的问题，原题：https://leetcode.com/problems/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):
1."123"
2."132"
3."213"
4."231"
5."312"
6."321"
Given n and k, return the kth permutation sequence.
然后呢，就想了想，看了看！还是想不通在下面这个代码里面为啥k要先减去1呢？？？因为之前没减去1，然后自己走了一遍发现是错的，然后减去1，可是我不知道是为啥呀？脑袋有点蒙，请大神指教!!
代码：
class Solution {
public:
string getPermutation(int n, int k) {
string s;
if(n < 0 || k < 0)
return "0";
int flag[n];
int num = 1;
for(int i = 0;i < n;++i)
{
flag[i] = i+1;//么有0，注意看题，是[1,2,3...n],不是从0开始,flag里面存储这些值
num *= (i+1);
}
k--;//这个地方k要先减去1？？？？
for(int i = 1;i <= n;i++)
{
int num = num/(n-i-1);
int selected = k/num ;
s.push_back('0' + flag[selected]);//转为字符
for(int j = selected;j < n-i-1;j++)
{
flag[j] = flag[j+1];
}
k = k%num;
}
return s;
}
};
这是一条镜像帖。来源：北邮人论坛 / cpp / #90009同步于 2016/1/23
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
leetcode全排列的问题
b1196027787
2016/1/23镜像同步5 回复
订阅后，新回复会通过你的通知中心匿名送达。
5 条回复
【 在 yxyyinxinyu 的大作中提到: 】
: 生成全排列……有字典序法 递增进位制法 递减进位制法 邻位对换法……第一种第四种比较好写
: 发自「贵邮」
递增进位法是什么意思呢？我感觉我想的是邻位对换法。。。
就是利用中介数 这个中介数最低位是二进制的 往前一位是三进制的 依此类推 然后每次生成新排列把这个中介数加一 另外通过中介数转化到排列 需要数对应数位的中介数是几表示对应数位的数字右侧有几个比他小的数字
说起来比较难懂 网上有例子
【 在 timruning 的大作中提到: 】
:
: 【 在 yxyyinxinyu 的大作中提到: 】
: : 生成全排列……有字典序法 递增进位制法 递减进位制法 邻位对换法……第一种第四种比较好写
: : 发自「贵邮」
: 递增进位法是什么意
: .........
发自「贵邮」