Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Permutation Sequence

Leetcode algorithms 第 60 题: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.

Note: Given n will be between 1 and 9 inclusive.

解答

求n个元素的全排列中的第k个。使用康托展开:

X=a[n]*(n-1)!+a[n-1]*(n-2)!+…+a[i]*(i-1)!+…+a[1]*0!

令i从n-1遍历到0,每次k除i的阶乘的结果即为a[n],表示该位置上的数字为当前剩下的数字中的第a[n]个,然后更新k的值为模i阶乘的余数。

具体代码如下:

class Solution {
public:
    string getPermutation(int n, int k) {
        int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
        
        k--;
        bool vs[10] = {0};
        string ans;
        for (int i = n-1; i >= 0; i--)
        {
            int t = k / fac[i]; k %= fac[i];
            int j, cnt = -1;
            for (j = 1; j <= n; j++)
            {
                if (!vs[j]) cnt++;
                if (cnt == t) break;
            }
            
            vs[j] = 1;
            ans += char(j + '0');
        }
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论