【Leetcode】60. 第k个排列
【Leetcode】60. 第k个排列
Leetcode名企之路
发布于 2018-09-12 15:23:54
发布于 2018-09-12 15:23:54
题目
给出集合 [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)后来这个版本提交的时候我以为可以洗洗睡啦. 结果,卧槽,居然换一种语言就超时啦~~
TLE
这倒是个意外.难道我的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 民法
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-09-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录