国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > Leetcode--Permutation Sequence

Leetcode--Permutation Sequence

来源:程序员人生   发布时间:2014-09-08 08:58:35 阅读次数:3267次

Problem Description:

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.

分析:

首先想到的暴力法,逐个的求排列,直到找到第k个排列,提交之后会超时,在网上搜索之后发现可以直接构造出第k个排列,以n = 4,k = 17为例,数组src = [1,2,3,...,n]。

第17个排列的第一个数是什么呢:我们知道以某个数固定开头的排列个数 = (n-1)! = 3! = 6, 即以1和2开头的排列总共6*2 = 12个,12 < 17, 因此第17个排列的第一个数不可能是1或者2,6*3 > 17, 因此第17个排列的第一个数是3。即第17个排列的第一个数是原数组(原数组递增有序)的第m = upper(17/6) = 3(upper表示向上取整)个数。                                       

第一个数固定后,我们从src数组中删除该数,那么就相当于在当前src的基础上求第k - (m-1)*(n-1)! = 17 - 2*6 = 5个排列,因此可以递归的求解该问题。

代码实现中注意一个小细节,就是一开始把k--,目的是让下标从0开始,这样下标就是从0到n-1,不用考虑n时去取余,更好地跟数组下标匹配。具体代码如下:

class Solution { public: int fun(int n) { if(n<0) return 0; else if(n==0) return 1; else return n*fun(n-1); } string getPermutation(int n, int k) { string s; int total=fun(n); if(total<k) return s; vector<int> flag(n,0); //因为数组是从0到n-1的,所以基数从0到k-1 --k; for(int i=0;i<n;i++) flag[i]=i+1; for(int i=0;i<n;i++) { total/=(n-i); int index=k/total; s.push_back('0'+flag[index]); for(int j=index;j<n-i-1;j++) flag[j]=flag[j+1]; k -= index*total; } return s; } };



生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生