# 题目

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321" 给定 n 和 k，返回第 k 个排列。

```输入: n = 3, k = 3

```输入: n = 4, k = 9

# 题解

1. 从小到大把数排好;
2. 用backtrack的方法遍历,每次遍历到一个全排列那么结果,count+1;
3. 遍历到n就return输出
4. 由于用的是backtrack,后面 count > k的情况都直接return掉;

```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;
}
haveSeen[i] = true;
backtrack(nums, k, tempIndex, haveSeen);
haveSeen[i] = false;
tempIndex.remove(tempIndex.size() - 1);
}
}
}```

```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

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 民法

83 篇文章21 人订阅

0 条评论

## 相关文章

36970

11310

12250

### 向前字典排序

next_permutation算法对区间元素进行一次组合排序，使之字典顺序大于原来的排序，有如下两个使用原形，对迭代器区间[first,l...

27990

406120

### BFPRT算法

首先将原数组分成5个一组，每组内进行排序，组间不排序，然后将每组的中位数取出再次进行上述操作，直到最后只能分成一组了，然后取出中位数，将这个中位数当作标尺进行...

11420

54960

34540

30670

35250