首页 > 代码库 > [leetcode]Permutation Sequence

[leetcode]Permutation Sequence

2024-07-13 17:03:54   226人阅读

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.

算法思路：

思路1：

最直观的思路，dfs逐个求，并计数。提交之后超时。

代码如下：

 1 public class Solution { 2     boolean success = false; 3     StringBuilder str = new StringBuilder(); 4     int count = 0; 5     public String getPermutation(int n, int k) { 6         int count = 1; 7         for(int i = 1; i <= n; count*=i++); 8         if(k <= 0 || k > count ) return null; 9         boolean[] hash = new boolean[10];10         for(int i = 1; i <= n;hash[i++] = true);11         StringBuilder sb = new StringBuilder();12         dfs(sb,hash,k,n);13         return str.toString();14     }15     private void dfs(StringBuilder sb,boolean[] set,int k,int n){16         if(sb.length() == n){17             count++;18             if(count == k) {19                 success = true;20                 str = sb;21             }22             return;23         }24         for(int i = 1; i <= n ; i++){25             if(!set[i]) continue;26             set[i] = false;27             sb.append(i);28             dfs(sb, set, k, n);29             if(success) return;30             set[i] = true;31             sb.deleteCharAt(sb.length() - 1);32         }33     }34     35 }
View Code

 

思路2：

跳过中间那些无用的，直接求第k个。

寻找规律：

以n = 4,k = 20为例。以1为头的字符串一共有3!= 6个，同理以2、3开头的也有6个，因此第20个必定以4开头。

接下来只需要求以4开头的第2（20 - 18）个即可。

再递归处理。

 1 public class Solution { 2     public String getPermutation(int n, int k) { 3         int count = 1; 4         for(int i = 1; i <= n; count*=i++); 5         if(k <= 0 || k > count ) return null; 6         List<Integer> list = new ArrayList<Integer>(); 7         for(int i = 1; i <= n; list.add(i++)); 8         StringBuilder sb = new StringBuilder(); 9         helper(n, k, list, sb);10         return sb.toString();11     }12     13     public void helper(int n,int k ,List<Integer> list,StringBuilder sb){14         if(n == 1) {15             sb.append(list.get(0));16             return;17         }18         int count = 1;19         for(int i = 1; i <= n - 1;count *= i++);20         int index = 0;21         while(k > count){22             index++;23             k -= count;24         }25         sb.append(list.get(index));26         list.remove(index);27         helper(n - 1,k,list,sb);28     }    29 }

 

 

思路3：

迭代处理

传递门


联系
我们