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。int[]数组是不能直接作为new String(array)的argument的。另一方面，这道题再次证实了数组是对象，而函数用对象做argument传的是对该对象的引用，在函数内改引用不会对原数组造成影响，但是在函数内改引用所指向的内容，就会有影响了。比如这里传数组num，而里面改num[i], 改的是内容，所以num改变了

 1 public class Solution {
 2     public String getPermutation(int n, int k) {
 3         char[] array = new char[n];
 4         for (int i=0; i<n; i++) {
 5             array[i] = (char)('0' + i + 1);
 6         }
 7         for (int i=1; i<k; i++) {
 8             helper(array);
 9         }
10         return new String(array);
11     }
12     
13     public void helper(char[] array) {
14         int i = 0;
15         int j = 0;
16         for (i=array.length-2; i>=0; i--) {
17             if (array[i] < array[i+1]) break;
18         }
19         if (i >= 0) {
20             for (j=i; j<array.length-1; j++) {
21                 if (array[j+1] <= array[i]) break;
22             }
23             char temp = array[i];
24             array[i] = array[j];
25             array[j] = temp;
26         }
27         reverse(array, i+1);
28     }
29     
30     public void reverse(char[] array, int index) {
31         int l = index;
32         int r = array.length - 1;
33         while (l < r) {
34             char temp = array[l];
35             array[l] = array[r];
36             array[r] = temp;
37             l++;
38             r--;
39         }
40     }
41 }

我这个方法很直接，但是时间复杂度O(N*k)应该比较大，因为k是可以取值到N!的，虽然通过了OJ，但是还是不太好。网上看到一些做法，均是把它当做一道找规律的数学题目。我们知道，n个数的permutation总共有n阶乘个，基于这个性质我们可以得到某一位对应的数字是哪一个。思路是这样的，比如当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，也就是(n-1)!个permutation后会换一个起始元素。因此，只要当前的k除以(n-1)!，得到的数字就是当前的index，如此就可以得到对应的元素，而k % (n-1)! 得到的数字就是当前剩余数组的index，如此递推直到数组中没有元素结束。实现中我们要维护一个数组来记录当前的元素，每次得到一个元素加入结果数组，然后从剩余数组中移除，因此空间复杂度是O(n)。时间上总共需要n个回合，而每次删除元素如果是用数组需要O(n),所以总共是O(n^2)。这里如果不移除元素也需要对元素做标记，所以要判断第一个还是个线性的操作。

第二遍做法：

LISHI's

We actually can calculate the sequence. For sequences with n numbers, it is composed by n segments of sequences with n-1 numbers. The number of (n-1) sequences in each segment is (n-1)!. So if we are looking for kth n sequence, it is in (k/(n-1)!)th or (k/(n-1)!+1)th segment (boundary case considerred) which is means the number in the first place should be the (k/(n-1)!)th available number between 1 and n. The number of sequences we should count in this segment to find the target is (k%(n-1)!)th sequence in this segement. With this recurrence formula, we can directly calculate the string one place by one place.

 1 public class Solution {
 2     public String getPermutation(int n, int k) {
 3         if (n<=0 || k<=0) return "";
 4         StringBuffer res = new StringBuffer();
 5         int factorial = 1;
 6         for (int i=2; i<n; i++) {
 7             factorial *= i;
 8         }
 9         ArrayList<Integer> num = new ArrayList<Integer>();
10         for (int i=1; i<=n; i++) {
11             num.add(i);
12         }
13         int round = n - 1;
14         k--;
15         while (round >= 0) {
16             int index = k / factorial;
17             k %= factorial;
18             res.append(num.get(index));
19             num.remove(index);
20             if (round > 0) {
21                 factorial /= round;
22             }
23             round--;
24         }
25         return res.toString();
26     }
27 }

说明：num数组中按顺序存着1-n这n个数；每找到一个index，把它加入res的同时，把该index元素从数组删除. 这样不会重复利用某个数组元素

k--目的是让下标从0开始，这样下标就是从0到n-1，更好地跟数组下标匹配（这样每(n-1)!个数它们的第一个元素都是一样的）。

factorial最开始是（n-1）！，然后（n-2）！。。。跟数组剩余元素个数有关（每次减一）

因为答案有n位，所以round有n轮，一轮确定一位数。这里因为正好factorial要依次除n-1, n-2, n-3...所以干脆就让round计数从n-1到0

Leetcode: Permutation Sequence

相关推荐