[leetcode]Permutation Sequence

算法还是一样的算法，但是新博文的代码更简洁，可读性更好，新博文地址：[leetcode]Permutation Sequence

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.

这道题思路很简单，但是实现起来用的时间比较长，可能是思路不太清晰，或者几天没做题手生了吧。题中要求是给出数字n，则由1~n可组成n！的组合，将组合数从小到大排序，求出第k个组合数。

 

最直观的思路无非是求出n！个组合情况，将其排序，然后求出第k个。事实上，想一下就知道这是不可能做到的，当n不需要很大，比如n = 100时，n！已经是很大的数了，可能已经溢出了，想其时间复杂度O(n!)更是早就超时了，因此不能这样做。

 

不得不换种思路，不需要求出所有的组合数。甚至直接求第K个组合数。到底该怎么做呢？

有几点条件是可以使用的。组合数都是从小到大排序的。去掉高位之后，低位数字同样从小到大排序，因此可以考虑用递归。

来看题中给的例子：

123 -- 第1个loop

132 -- 第1个loop

213 -- 第2个loop

231 -- 第2个loop

312 -- 第3个loop

321 -- 第3个loop

我们可以根据k确定最高位的数字：

因为去掉最高位还剩下2位，这两位数字可以组成(n - 1)!种组合（记作factorial），再求出其在哪个loop中

如果k <=  factorial，肯定在第1个loop，如果k > factorial，比如k = 5，那么应该在 5 / 2 = 2第2个loop，但是当k = 6时，在6/ 2个loop，但是k = 5或k = 6是在同一个loop中，区别就是一个有余数，一个是整除，简单处理之。

好了，当k = 5，求出第一位应该是3，然后标记3已经用过了，跨过了两个loop，即跨过了loop * factorial——4种组合，只需要递归从1、2组成的组合中找到第1个子组合即可。

 

大致算法思想就是这样。出口为确定了n位数字或者k = 1（这个自己想哈）

代码实现为：

 

public String getPermutation(int n, int k) {
		boolean[] hash = new boolean[n];
		if (n < 1) {
			return null;
		}
		int factorial = 1;
		for (int i = 0; i < n; hash[i] = true, factorial *= (1 + i), i++);
		if (factorial < k) {
			return null;
		}
		return dfs(hash, k, 0);
	}

	/**
	 * @param hash
	 * @param k
	 *            means find the k_th number in factorial
	 * @param n
	 *            means has confirmed n prefix numbers
	 * @return
	 */
	private String dfs(boolean[] hash, int k, int n) {
		StringBuilder sb = new StringBuilder();
		if(n == hash.length){
			return "";
		}
		if (k == 1) {
			int i = 0;
			while (i < hash.length) {
				if (hash[i]) {
					sb.append(i + 1);
				}
				i++;
			}
			return sb.toString();
		}
		int factorial = 1;
		for (int i = 1; i <= hash.length - n - 1; factorial *= i, i++);
		int loop = 0;
		if (k > factorial) {
			loop = k / factorial + 1;
			if(k % factorial == 0) loop--;
		} else {
			loop = 1;
		}
		for (int count = 0, i = 0; i < hash.length; i++) {
			if (hash[i]) {
				count++;
				if (count == loop) {
					sb.append(i + 1);
					hash[i] = false;
					break;
				}
			}
		}
		if(k > factorial) return sb.append(dfs(hash, k - (loop - 1)* factorial, n + 1 )).toString();
		else return sb.append(dfs(hash, k, n + 1)).toString();
	}