首页 > 代码库 > leetcode Permutation Sequence

leetcode Permutation Sequence

题目:给定数字n,然后将1到n的第k个字典序排列找出来,例如3的时候有所有字典序为:

"123" "132" "213" "231" "312" "321"  那么第2个就是“132”,返回这个字符串。

记得之前有做过输出所有可能的排序,在Permutation中,有兴趣还可以看看。所以很直观的就是复制那题的代码然后返回第k个就完事了。因为只要一分钟,所以我试了一下,果断是不行啊,提示超时,那题是用递归做的。所以我们肯定是有方法不用求所有的啊。然后我就开始从数学角度进入探索了。发现和(n-1)!有巧妙的关系,就是用k-1除以(n-1)!再加一(但看下标的话不用加1)之后的值其实就是第k个排列中的第一个数。然后我也想到了用k减去相应的数,然后再计算接下去的是什么数,但是后面的数字乱掉了,因为不是按照顺序了。比如如果第一个数是2,那么后面就是1,3了,所以我没想到用k可以表示它的方法。其实就差一步就做出来了。哎。原来可以按下标输出,不用找数字和k的关系,而是记录下标和k的关系。看了这个大神的。觉得好赞。记录下:

思路:

n个数的的第k个排列为:

a1, a2, a3,...an;

接下来我们一个一个数的选取,如何确定第一个数应该是哪一个呢?选取第一个数后剩下全排列的个数为(n-1)! 所以选取的第一个数应该为第

K1 = k;

a1 = K1/(n-1)!位数字

同理当选完a1后只剩下n-1个数字,在确定第二个数应该选择哪个.

a2 = K2 / (n-2)!

K2 = K1 % (n-1)!

........

a(n-1) = K(n-1) / 1!

K(n-1) = k(n-2) % 2!

an = K(n-1)

代码:

class Solution {  public:      string getPermutation(int n, int k) {        vector<int> num(n, 0);        int perm_sum = 1;        for(size_t i = 0; i < n; ++i)        {          num[i] = i + 1;          perm_sum *= (i + 1);        }        string ret;        //因为数组是从0到n-1的 所以基数从 0到k-1        --k;        for(size_t i = 0; i < n; ++i)        {          perm_sum = perm_sum / (n - i);          int selected = k / perm_sum;          ret.push_back(num[selected] + 0);          //选择一个数后重新构造剩下的数组          for(size_t j = selected; j < n - i - 1; ++j)            num[j] = num[j + 1];          k = k % perm_sum;        }        return ret;      }  };

我觉得这个妙在阶乘只求了一次,然后用后面的数覆盖已经选出来的数,即数组往前,这样每次都按照下标0开始即可。

 

leetcode Permutation Sequence