首页 > 代码库 > leetcode Permutation Sequence

leetcode Permutation Sequence

2024-08-03 06:19:14   221人阅读

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个值。

以n = 4，k = 17为例，数组src = http://www.mamicode.com/[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个排列，因此可以递归的求解该问题。

 

 1 public class Solution { 2     String NUM="123456789"; 3     String s; 4     int mk; 5     public String getPermutation(int n, int k) { 6         s=NUM.substring(0, n); 7         mk=k; 8         String res=""; 9         for (int i = 0; i < n; i++) {10             res=res+helper();11         }12         13         return res;14     }15     /*返回下一个数字*/16     char helper(){17         int tmp=fact(s.length()-1),i=(mk-1)/tmp;18         char res = s.charAt(i);19         s=s.substring(0,i)+s.substring(i+1, s.length());20         mk=mk-i*tmp;21         return res;22         23     }
　　　　/*计算n!*/24     int fact(int n){25         int res = 1;26          for(int i = 2; i <= n; i++)27              res *= i;28          return res;29         30     }31     32 }

 

leetcode Permutation Sequence


联系
我们