题目
给出集合 [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 China
in public
Republicans (n.)共和主义者
mass (n.)群众 (v.)聚集 (a. 集中的)
masses of = many
civilian (a.)平民
civil law 民法
相关阅读
46. 全排列
47. 全排列 II