题目给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：“123"“132"“213"“231"“312"“321"给定 n 和 k，返回第 k 个排列。说明：给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。示例 1:输入: n = 3, k = 3输出: “213"示例 2:输入: n = 4, k = 9输出: “2314"题解这道题还蛮有意思的,我首先一看,这不是backtrack的经典题目吗? backtrack的剪枝可以参看相关文章中有详细的step-by-step的流程.从小到大把数排好;用backtrack的方法遍历,每次遍历到一个全排列那么结果,count+1;遍历到n就return输出由于用的是backtrack,后面 count > k的情况都直接return掉;然后用java写了一个版本,还没有剪枝就ac啦.class Solution {int count = 0; List<Integer> finalRes; public String getPermutation(int n, int k) { int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = i + 1; } //第几个解. List<Integer> resTemp = new ArrayList<>(); boolean[] haveSeen = new boolean[n]; backtrack(nums, k, resTemp, haveSeen); StringBuilder res = new StringBuilder(); for (Integer i : finalRes) { res.append(i); } return res.toString(); } public void backtrack(int[] nums, int k, List<Integer> tempIndex, boolean[] haveSeen) { if (tempIndex.size() == nums.length) { count++; } if (count == k && tempIndex.size() == nums.length) { finalRes = new ArrayList<>(tempIndex); return; } else if (count < k && tempIndex.size() == nums.length) { tempIndex = new ArrayList<>(); } for (int i = 0; i < nums.length; i++) { if (haveSeen[i]) { continue; } tempIndex.add(nums[i]); haveSeen[i] = true; backtrack(nums, k, tempIndex, haveSeen); haveSeen[i] = false; tempIndex.remove(tempIndex.size() - 1); } }}由于前几天后台有同学反馈,希望给出java版本的题解。所以又动手写了一个python版本.class Solution: def getPermutation(self, n, k): "”” :type n: int :type k: int :rtype: str "”” global count global finalRes count = 0 finalRes = [] def backtrack(nums, k, resTemp, haveSeen): global count global finalRes if count > k: return if len(resTemp) == len(nums): count += 1 if count == k and len(resTemp) == len(nums): finalRes = [str() for _ in resTemp] return elif count < k and len(resTemp) == len(nums): resTemp = [] for i in range(0, len(nums)): if count > k: break if haveSeen[i]: continue resTemp.append(nums[i]) haveSeen[i] = True backtrack(nums, k, resTemp, haveSeen) haveSeen[i] = False resTemp.pop() backtrack([ + 1 for _ in range(0, n)], k, [], [False for _ in range(0, n)]) return “".join(finalRes)后来这个版本提交的时候我以为可以洗洗睡啦.结果,卧槽,居然换一种语言就超时啦~~这倒是个意外.难道我的python写的有性能问题,不应该啊,不是：人生苦短,我用python我就继续想剪枝,还能怎么剪枝?剪枝是啥，不就是跳过某些步骤吗？那哪些步骤可以跳过呢.4的全排列是: 1 + {2,3,4}全排列2 + {1,3,4}全排列3 + {1,2,4}全排列4 + {1,2,3}全排列似乎可以转化成子问题啊.由于题目只要求出第几个,我们再看看个数的规律1 + {2,3,4}全排列(3!个)2 + {1,3,4}全排列(3!个)3 + {1,2,4}全排列(3!个)4 + {1,2,3}全排列(3!个)这就很好了呀~具体来说是：n 个数字有 n！种全排列，每种数字开头的全排列有 (n - 1)!种。所以用 k / (n - 1)! 就可以得到第 k 个全排列是以第几个数字开头的。用 k % (n - 1)! 就可以得到第 k 个全排列是某个数字开头的全排列中的第几个。数学之美啊,有木有。然后就快速实现了python的code AC了.class Solution: def getPermutation(self, n, k): nums = [str(_ + 1) for _ in range(0, n)] if k == 1: return “".join(nums) fact = 1 for i in range(2, n): fact *= i round = n - 1 k -= 1 finalRes = [] while round >= 0: index = int(k / fact) k %= fact finalRes.append(nums[index]) nums.remove(nums[index]) if round > 0: fact /= round round -= 1 return “".join(finalRes)每日英文pulicity (n.) 曝光度,知名度enhanace the ~ of yourself 提高自己的知名度publication (n.) 刊物,发表Publicize (v.) 宣传issue (v.) 发表People’s Republic Of Chinain publicRepublicans (n.)共和主义者mass (n.)群众 (v.)聚集 (a.集中的)masses of = manycivilian (a.)平民civil law 民法相关阅读46.全排列47. 全排列 II