Leetcode 60. 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):

Given n and k, return the kth permutation sequence.

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

标签 Backtracking Math

类似题目 (M) Next Permutation (M) Permutations

思路:

1.对于由{1,2,...,n}组成的第k个数(k从0开始),k = a * (n-1)! + b,其中a表示的是{1,2,...,n}中第a个数,b表示的是由{1,2,...,n}去掉第a个数后剩下的数(维持升序排列)构成的数组成的排列的第b个排列。

2.k = b,重复1共n次。

代码:

 1 public class Solution {
 2     public String getPermutation(int n, int k) {
 3         List<Integer> numbers = new ArrayList<>();
 4         int[] factor = new int[n];
 5         int i, t;
 6         String res = "";
 7         factor[0] = 1;
 8         for (i = 1; i < n; ++i)    factor[i] = factor[i - 1] * i;
 9         for (i = 1; i <= n; ++i) numbers.add(i);
10         k--;
11         for (i = n - 1; i >= 0 ; --i) {
12             t = k / factor[i];
13             res = res + numbers.get(t);
14             k = k % factor[i];
15             numbers.remove(t);
16         }
17         return res;
18     }
19 }
时间: 03-20

Leetcode 60. Permutation Sequence的相关文章

leetcode 60 Permutation Sequence ----- java

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" "3

leetCode 60.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" "

19.2.9 [LeetCode 60] 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 for n = 3: "123" "132" "213" "231" "312" "321&

【leetcode】 Permutation Sequence

问题: 对于给定序列1...n,permutations共有 n!个,那么任意给定k,返回第k个permutation.0 < n < 10. 分析: 这个问题要是从最小开始直接到k,估计会超时,受10进制转换为二进制的启发,对于排列,比如 1,2,3 是第一个,那么3!= 6,所以第6个就是3,2,1.也就是说,从开始的最小的序列开始,到最大的序列,就是序列个数的阶乘数.那么在1,3 , 2的时候呢?调整一下,变成2,1,3,就可以继续. 实现: int getFactorial(int n

【一天一道LeetCode】#60. Permutation Sequence.

一天一道LeetCode系列 (一)题目 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 :&quo

60. Permutation Sequence java solutions

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" "3

60. 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" "3

【leetcode】 Permutation Sequence (middle)

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" "3

[C++]LeetCode: 114 Permutation Sequence(返回第k个阶乘序列——寻找数学规律)

题目: 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" &q