首页 > 其他 > 详细

LC60 Permutation Sequence

时间:2016-04-02 20:16:10      阅读:180      评论:0      收藏:0      [点我收藏+]

这道题目有两种做法,第一种是把排列一直列到第k个。另一种做法是利用康托编码,如果把n!个排列根据首个数字大小排列成n组,则每一组有(n-1)!个元素,求第k个排列,可以先令p=k/(n-1)! 求出第一个数字num[p].

然后递归做下去。更新数字k=k%(n-1)!,并在数组num中删除num[p]。如果把(n-1)!个排列根据第二个数字大小排列成(n-1)组,则每一组有(n-2)!个元素,求第k个排列,可以令p=k/(n-2)! 求出第二个数字num[p].

这样直到数组num中只有一个元素为止。

要特别注意,康托编码的第k个排列是从0开始数的。

技术分享
 1 class Solution {
 2 public:
 3     string getPermutation(int n, int k) {
 4         string s="";
 5         if(n<=0||k<=0)
 6             return s;
 7         int tmp=1;
 8         string str(n,0);
 9         for(int i=1;i<=n;i++)
10         {
11             str[i-1]+=i;
12             tmp*=i;
13         }
14         tmp=tmp/n;
15         k--;
16         for(int i=n-1;i>0;i--)
17         {
18             int p=k/tmp;
19             k=k%tmp;
20             s+=string(1,str[p]);
21             str.erase(str.begin()+p);
22             tmp=tmp/i;
23         }
24         s+=string(1,str[0]);
25         return s;
26     }
27 };
View Code

 

LC60 Permutation Sequence

原文:http://www.cnblogs.com/vaecn/p/5348064.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!