首页 > 代码库 > Leetcode: Permutation Sequence
Leetcode: 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):"123""132""213""231""312""321"Given n and k, return the kth permutation sequence.Note: Given n will be between 1 and 9 inclusive.
看到这道题，第一时间就联系到了Next Permutation. 那道题是让找下一个稍大的Permutation, 而这里是找从小到大第K大的Permutation, 而最小的Permutation我们明显知道，那么用Next Permutation做Subroutine，做K次，不就找到了所需的Permutation了吗。Next Permutation时间复杂度为O(N), 这里就是O(N*k).
代码里面把Int数组拷贝成一个char数组，是为了方便转换成String
1 public class Solution { 2 public String getPermutation(int n, int k) { 3 if (n < 0) return""; 4 int[] num = new int[n]; 5 char[] numcopy = new char[n]; 6 for (int z=0; z<n; z++) { 7 num[z] = z + 1; 8 } 9 for (int i=2; i<=k; i++) {10 nextPermutation(num);11 }12 for (int z=0; z<n; z++) {13 numcopy[z] = (char)(‘0‘ + num[z]);14 }15 return new String(numcopy);16 }17 18 public void nextPermutation(int[] num) {19 if (num == null || num.length == 0 || num.length == 1) return;20 int i = num.length-2;21 while (i>=0 && num[i]>=num[i+1]) {22 i--;23 }24 if (i >= 0) {25 int j = i;26 while (j<num.length-1 && num[j+1]>num[i]) {27 j++;28 }29 int temp = num[i];30 num[i] = num[j];31 num[j] = temp;32 }33 reverse(num, i+1);34 }35 36 public void reverse(int[] num, int k) {37 int start = k;38 int end = num.length - 1;39 while (start < end) {40 int temp = num[start];41 num[start] = num[end];42 num[end] = temp;43 start++;44 end--;45 }46 }47 }
我这个方法很直接，但是时间复杂度O(N*k)应该比较大，因为k是可以取值到N!的，虽然通过了OJ，但是还是不太好。 网上看到一些做法，均是把它当做一道找规律的数学题目。我们知道，n个数的permutation总共有n阶乘个，基于这个性质我们可以得到某一位对应的数字是哪一个。思路是这样的，比如当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，也就是(n-1)!个permutation后会换一个起始元素。因此，只要当前的k进行(n-1)!取余，得到的数字就是当前剩余数组的index，如此就可以得到对应的元素。如此递推直到数组中没有元素结束。实现中我们要维护一个数组来记录当前的元素，每次得到一个元素加入结果数组，然后从剩余数组中移除，因此空间复杂度是O(n)。时间上总共需要n个回合，而每次删除元素如果是用数组需要O(n),所以总共是O(n^2)。这里如果不移除元素也需要对元素做标记，所以要判断第一个还是个线性的操作。
Code Ganker做法（未深究）
1 public String getPermutation(int n, int k) { 2 if(n<=0) 3 return ""; 4 k--; 5 StringBuilder res = new StringBuilder(); 6 int factorial = 1; 7 ArrayList<Integer> nums = new ArrayList<Integer>(); 8 for(int i=2;i<n;i++) 9 {10 factorial *= i;11 }12 for(int i=1;i<=n;i++)13 {14 nums.add(i);15 }16 int round = n-1;17 while(round>=0)18 {19 int index = k/factorial;20 k %= factorial;21 res.append(nums.get(index));22 nums.remove(index);23 if(round>0)24 factorial /= round;25 round--;26 }27 return res.toString();28 }
Leetcode: Permutation Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。