算法leetcode｜60. 排列序列（rust重拳出击）

文章目录

60. 排列序列：

给出集合

[1,2,3,...,n]

，其所有元素共有

n!

种排列。

按大小顺序列出所有排列情况，并一一标记，当

n = 3

时, 所有排列如下：

"123"

"132"

"213"

"231"

"312"

"321"

给定

n

和

k

，返回第

k

个排列。

样例 1：

输入：
    
    n = 3, k = 3
    
输出：
    
    "213"

样例 2：

输入：
    
    n = 4, k = 9
    
输出：

    "2314"

样例 3：

输入：
    
    n = 3, k = 1
    
输出：
    
    "123"

提示：

• 1 <= n <= 9
• 1 <= k <= n!

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 如果模拟，按顺序生成k个序列，那效率实在太低了。
• 需要找到规律，直接去生成结果，这时候要用到一点数学知识，不是高数哈，是排列组合的知识，应该是高中的知识吧，也有可能是初中的，总之你肯定知道：1. n个元素排列，排列的总数为n!。 …
• 可以推出如果有n个元素排列，那么第一个位置会在(n - 1)!次排列后换下一个元素。
• 比如 4 个元素 [1, 2, 3, 4] 排列，第一个位置先是1，会在 3 * 2 * 1 个排列（也就是3个元素排列的总数3!）之后，第一个位置开始排 2，即：1. 12342. 12433. 13244. 13425. 14236. 14327. 2134 …
• 所以我们可以直接用 (k - 1) / (n - 1)! + 1 来计算第一个位置是第几个元素。
• 而接下来计算第二个位置的元素其实也是同计算第一个位置的元素是相似的，唯一的不同就是第一个位置的元素已经被占用了，所以后面要排除掉，因此要记录下哪个元素用过，哪个元素没有用过，后面就都是相同的子问题了。

题解：

rust：

implSolution{pubfnget_permutation(n:i32, k:i32)->String{let n = n asusize;letmut k = k asusize;// 结果letmut ans =String::new();// 阶乘缓存不同排列数letmut factorial =vec![0; n];
        factorial[0]=1;(1..n).for_each(|i|{
            factorial[i]= factorial[i -1]* i;});// 排列从0编号，便于后面计算
        k -=1;// 1为有效还没有占用，0为无效已经被占用letmut valid =vec![1; n +1];(1..n +1).for_each(|i|{// 计算当前位置的数字是第几个没被占用的数字letmut order = k / factorial[n - i]+1;for j in1..n +1{// 取得数字
                order -= valid[j];if order ==0{
                    ans.push((j asu8+b'0')aschar);
                    valid[j]=0;break;}}// 余数为下级子排列的序号
            k %= factorial[n - i];});return ans;}}

go：

funcgetPermutation(n int, k int)string{// 结果
    ans :=""// 阶乘缓存不同排列数
    factorial :=make([]int, n)
    factorial[0]=1for i :=1; i < n; i++{
        factorial[i]= factorial[i-1]* i
    }// 排列从0编号，便于后面计算
    k--// 1为有效还没有占用，0为无效已经被占用
    valid :=make([]int, n+1)for i :=0; i <len(valid); i++{
        valid[i]=1}for i :=1; i <= n; i++{// 计算当前位置的数字是第几个没被占用的数字
        order := k/factorial[n-i]+1for j :=1; j <= n; j++{// 取得数字
            order -= valid[j]if order ==0{
                ans += strconv.Itoa(j)
                valid[j]=0break}}// 余数为下级子排列的序号
        k %= factorial[n-i]}return ans
}

c++：

classSolution{public:
    string getPermutation(int n,int k){// 结果
        string ans;// 阶乘缓存不同排列数
        vector<int>factorial(n);
        factorial[0]=1;for(int i =1; i < n;++i){
            factorial[i]= factorial[i -1]* i;}// 排列从0编号，便于后面计算--k;// 1为有效还没有占用，0为无效已经被占用
        vector<int>valid(n +1,1);for(int i =1; i <= n;++i){// 计算当前位置的数字是第几个没被占用的数字int order = k / factorial[n - i]+1;for(int j =1; j <= n;++j){// 取得数字
                order -= valid[j];if(!order){
                    ans +=(j +'0');
                    valid[j]=0;break;}}// 余数为下级子排列的序号
            k %= factorial[n - i];}return ans;}};

python：

classSolution:defgetPermutation(self, n:int, k:int)->str:# 结果
        ans =list()# 阶乘缓存不同排列数
        factorial =[1]for i inrange(1, n):
            factorial.append(factorial[-1]* i)# 排列从0编号，便于后面计算
        k -=1# 1为有效还没有占用，0为无效已经被占用
        valid =[1]*(n +1)for i inrange(1, n +1):# 计算当前位置的数字是第几个没被占用的数字
            order = k // factorial[n - i]+1for j inrange(1, n +1):# 取得数字
                order -= valid[j]if order ==0:
                    ans.append(str(j))
                    valid[j]=0break# 余数为下级子排列的序号
            k %= factorial[n - i]return"".join(ans)

java：

classSolution{publicStringgetPermutation(int n,int k){// 结果finalStringBuilder ans =newStringBuilder();// 阶乘缓存不同排列数finalint[] factorial =newint[n];
        factorial[0]=1;for(int i =1; i < n;++i){
            factorial[i]= factorial[i -1]* i;}// 排列从0编号，便于后面计算--k;// 1为有效还没有占用，0为无效已经被占用finalint[] valid =newint[n +1];Arrays.fill(valid,1);for(int i =1; i <= n;++i){// 计算当前位置的数字是第几个没被占用的数字int order = k / factorial[n - i]+1;for(int j =1; j <= n;++j){// 取得数字
                order -= valid[j];if(order ==0){
                    ans.append(j);
                    valid[j]=0;break;}}// 余数为下级子排列的序号
            k %= factorial[n - i];}return ans.toString();}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~