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):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

如果挨个搜的话，恐怕会超时。

那就用算的方式，以n=3, k=3为例：

由于我们是从0开始计数，k -= 1；

首先，初始化一个链表list，list中的元素依次为：1, 2, 3；

获取第一位数字：k / 2! = 1，第一个数字就是list.get(1) = 2，同时，从链表中删除已经使用的元素list.remove(1)，list剩余数字：1, 3，并且k = k % 2! = 0；

获取第二个数字：k / 1! = 0，第二个数字就是list.get(0) = 1，同时，从链表中删除已经使用的元素list.remove(0)，list剩余数字：3，由于已达到最后一位，不需要操作k了。

获取第三个（最后）数字：list剩余的元素，即list.get(0) = 3。

最终三个数字为213。

按照这个思路代码如下。

代码

import java.util.LinkedList;
import java.util.List;

public class PermutationSequence {
	public String getPermutation(int n, int k) {
		// get permutation num
		int[] permutation = new int[n];
		permutation[0] = 1;
		for (int i = 1; i < n; ++i) {
			permutation[i] = permutation[i - 1] * (i + 1);
		}

		// num list that can be used
		List<Integer> list = new LinkedList<Integer>();
		for (int i = 1; i <= n; ++i) {
			list.add(i);
		}

		// process
		StringBuilder sb = new StringBuilder();
		int pos = n - 1;
		k -= 1;
		while (pos > 0) {
			int index = k / permutation[pos - 1];
			sb.append(list.get(index));
			list.remove(index);
			k = k % permutation[pos];
			--pos;
		}
		sb.append(list.get(0));
		return sb.toString();
	}
}

LeetCode | Permutation Sequence,布布扣,bubuko.com

LeetCode | Permutation Sequence

原文：http://blog.csdn.net/perfect8886/article/details/21858643