题目
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=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