首页 > 代码库 > Leetcode 60. Permutation Sequence
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.
标签
类似题目
思路:
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 }
Leetcode 60. Permutation Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。