恩施公司做网站,网站背景图片代码,网站建设方案书个人,网站建设类的公司名怎么起给出集合 [1,2,3,...,n]#xff0c;其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况#xff0c;并一一标记#xff0c;当 n 3 时, 所有排列如下#xff1a;
123132213231312321
给定…给出集合 [1,2,3,...,n]其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况并一一标记当 n 3 时, 所有排列如下
123132213231312321
给定 n 和 k返回第 k 个排列。 示例 1
输入n 3, k 3
输出213示例 2
输入n 4, k 9
输出2314示例 3
输入n 3, k 1
输出123提示
1 n 91 k n!
解题思路
例如 n 4 k 9 可以知道全排列有4*3*2*1 24种如下红色框住的为第9个 从上图可知以1开头的全排列 (4-1)! 6 共6种 9 / 6 1······3也就是该数位于2开头的第三个。 同理第一位2确定后剩下三位 1 3 4接下来需要确定第二位 由上面的图片可知 1 3 4全排列每一列分别有两个数3-13 / 2 1······1可知位于第二列开头的第一个
然后确定第三位 第三位则还剩下2个数1和4 1和4的全排列 1 4排列每类2-1)! 11 / 1 1·····0,可知位于1开头的第一个 最后一位数只有一种情况: 1-1) 1 具体算法如下
1、定义一个逆康托数组记录n位数字对应每个数字开头序列的个数例如4位数prenum[1, 1, 2, 6]
将k值-1再进行计算这里-1是为了 9 % 6 3而数组下标从0开始-1后方便计算。
2、定义一个valid数组[0.....n];记录还没有被使用的数字 已经使用的需要移除
3、(k -1 ) / prenum[n - i - 1] 1就是分别计算每一位数字位于那一列例如 9 -1/ 6 1 2说明第一个数字为2ans累加vali[2] ,2被使用后erase掉valid中剩余[0,1,3,4] 然后k记录剩余未计算的数 8 % 6 2 k 2再重复计算可得到 2/2 1 2; 再取走valid中的第2个 同理依次取完。 完整代码如下
class Solution {
public:string getPermutation(int n, int k) {//prenum {0!, 1!, 2!, 3!, .....(n-1)!}vectorint pernum(n);pernum[0] 1;for(int i 1; i n; i) {pernum[i] pernum[i-1] * i;}//k-- 方便取余后计算k--;string ans;vectorint valid(n1);//生成[0,1,2....n]的数组iota(valid.begin(), valid.end(), 0);for(int i 0; i n; i) {int order k / pernum[n-i-1] 1;ans (valid[order] 0);//用了就从数组中删除valid.erase(valid.begin() order);k % pernum[n-i-1];}return ans;}
}; 拓展康托展开也就是在全排列中给定一个序列求该序列位于第几个。
#include iostream
#include string
using namespace std;class Solution {public://求阶乘int fact(int x) {int ret 1;for(int i 2; i x; i) {ret * i;}return ret;}int getStringId(string str) {int len str.size();int ans 0;for(int i 0; i len; i) {int cnt 0;//记录后面的数有几个比当前的数小//例如2314 314中只有1个数比第一位小说明该数位于第二列。for(int j i 1 ; j len; j) {if(str[j] str[i]) {cnt ;}}ans cnt*fact(len- i -1);}return ans1;}
};
int main()
{string s;cin s;Solution sol;cout 位于序列第 sol.getStringId(s) 位 endl;return 0;
}
