首页 > 代码库 > LeetCode: Permutation Sequence 解题报告
LeetCode: Permutation Sequence 解题报告
Permutation Sequence
https://oj.leetcode.com/problems/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 kthpermutation sequence.
Note: Given n will be between 1 and 9inclusive.
解答：
1. 以某一数字开头的排列有(n-1)! 个。
例如： 123， 132， 以1开头的是 2！个
2. 所以第一位数字就可以用 （k-1） / (n-1)! 来确定.这里K-1的原因是，序列号我们应从0开始计算，否则在边界时无法计算。
3. 第二位数字。假设前面取余后为m，则第二位数字是 第 m/(n-2)! 个未使用的数字。
4. 不断重复2，3，取余并且对(n-k)!进行除法，直至计算完毕
以下为主页君的代码，敬请指正：
解法1：
采用比较复杂的boolean来计算数字的索引（我们需要用一个boolean的数组来记录未使用的数字）：
1 package Algorithms.permutation; 2 3 /* 4 The set [1,2,3,…,n] contains a total of n! unique permutations. 5 6 By listing and labeling all of the permutations in order, 7 We get the following sequence (ie, for n = 3): 8 9 "123"10 "132"11 "213"12 "231"13 "312"14 "321"15 16 Given n and k, return the kth permutation sequence.17 18 Note: Given n will be between 1 and 9 inclusive.19 * */20 public class PermutationSequence {21 public static String getPermutation(int n, int k) {22 if (n == 0) {23 return "";24 }25 26 // 先计算出(n)!27 int num = 1;28 for (int i = 1; i <= n; i++) {29 num *= i;30 }31 32 boolean[] use = new boolean[n];33 for (int i = 0; i < n; i++) {34 use[i] = false;35 }36 37 // 因为index是从0开始计算 38 k--;39 StringBuilder sb = new StringBuilder();40 for (int i = 0; i < n; i++) {41 // 计算完第一个数字前，num要除以(n)42 num = num / (n - i);43 44 int index = k / num;45 k = k % num;46 47 for (int j = 0; j < n; j++) { 48 if (!use[j]) {49 if (index == 0) {50 // 记录下本次的结果.51 sb.append((j + 1) + "");52 use[j] = true;53 break;54 }55 56 // 遇到未使用过的数字，记录index57 index--;58 }59 }60 }61 62 return sb.toString();63 }64 65 public static void main(String[] args) {66 System.out.println(getPermutation(3, 5));67 }68 69 }
解法2：
优化后，使用链表来记录未使用的数字，每用掉一个，将它从链表中移除即可。
1 public String getPermutation1(int n, int k) { 2 // 1:17 -> 1:43 3 LinkedList<Character> digits = new LinkedList<Character>(); 4 5 // bug 2: should only add n elements. 6 for (char i = ‘1‘; i <= ‘0‘ + n; i++) { 7 digits.add(i); 8 } 9 10 k = k - 1;11 StringBuilder sb = new StringBuilder();12 13 int sum = 1;14 // n!15 for (int i = 1; i <= n; i++) {16 sum *= i;17 }18 19 int cur = n;20 while (!digits.isEmpty()) {21 sum /= cur;22 cur--;23 24 int digitIndex = k / sum;25 k = k % sum;26 //Line 25: error: cannot find symbol: method digits(int)27 sb.append(digits.get(digitIndex));28 // remove the used digit.29 digits.remove(digitIndex);30 }31 32 return sb.toString();33 }
解法3：
在2解基础进一步优化，使用for 循环替代while 循环，更简洁：
1 public String getPermutation(int n, int k) { 2 // 1:17 -> 1:43 3 LinkedList<Character> digits = new LinkedList<Character>(); 4 5 // bug 2: should only add n elements. 6 for (char i = ‘1‘; i <= ‘0‘ + n; i++) { 7 digits.add(i); 8 } 9 10 // The index start from 0;11 k--;12 StringBuilder sb = new StringBuilder();13 14 int sum = 1;15 // n!16 for (int i = 1; i <= n; i++) {17 sum *= i;18 }19 20 for (int i = n; i >= 1; i--) {21 sum /= i;22 int digitIndex = k / sum;23 k = k % sum;24 25 //Line 25: error: cannot find symbol: method digits(int)26 sb.append(digits.get(digitIndex));27 28 // remove the used digit.29 digits.remove(digitIndex);30 }31 32 return sb.toString();33 }
GitHub代码链接
LeetCode: Permutation Sequence 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。