LeetCode 题解：一顿操作猛如虎，一看击败百分五
题目描述
给出集合 [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"
来源：https://leetcode-cn.com/problems/permutation-sequence
题目解析
一道比较偏数学的题目。
题意是给定 1 ～ n 的数字（n <= 9），因为数字所在的位置不同，这些数字可以组成的整数也不同。最后让你求按照组成的整数大小排序，排在第 k 的整数是多少。
要求全排列的话，时间和空间复杂度都是 O(n!)。
先看最直接的解法，通过暴力搜索，找出所有的全排列的情况，然后排序，直接就可以得出答案。
这么做的时间复杂度是 O(n!log(n!))。
很显然的是，这么做时间上面不符合要求，需要进一步优化算法。
首先考虑的一个问题是，我们需不需要找出所有的组合情况？
如果要找出所有的情况，那么时间上肯定是没法提高的。这其实就涉及到一个暴力搜索的剪支的问题，就拿 n = 3 为例，按照元素大小，全排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
这里，如果说 k = 5，那么是不是可以说以 “1” 和 “2” 开始的情况我们就不需要考虑了？
我们只需要从 “3” 开始的序列开始找就可以了，这样子可以很大程度上节省搜索的成本。
那么问题来了，如何确定我们需要找的结果在不在以某个数字开头的区间内？
其实，每个数字开头的序列总个数都是一样的，比如上面的以 “1”，“2”，“3” 开头的序列个数都是 2 个，我们只需要逐个排除就行了。
如果 k = 5，因为 5 > 2，说明结果不会在以 “1” 开头的区间中。又因为 5 > 4，说明结果不会在以 “2” 开头的区间中。
但是 5 < 6 的，所以我们需要在开头是 “3” 的序列中继续找。确定了开头数字是 3 之后，我们可以把 3 排除，然后继续去用同样的方法确定第二个数字，第三个数字。。。
这样做下来，时间上面是可以大大提高的。至于具体的时间复杂度是多少，这和具体的输入有关。但是空间方面，我们并不需要 O(n!) 的空间，n 的空间（函数栈空间）就足够了。
参考代码
func getPermutation(n int, k int) string {
nums := []int{}
for i := 1; i <= n; i++ {
nums = append(nums, i)
}
return helper(nums, k)
}
func helper(nums []int, k int) string {
totalNums := 1
// 计算以每个数字开头的序列个数
for i := 1; i < len(nums); i++ {
totalNums *= i
}
for i := range nums {
// 以当前数字开头的话，前面的序列的总个数
sum := (i + 1) * totalNums
sub := k - sum
// 说明结果是以当前数字开头
// 去掉当前选中的数字，递归去确定接下来的数字
if sub <= 0 {
arr := []int{}
arr = append(arr, nums[:i]...)
arr = append(arr, nums[i+1:]...)
return strconv.Itoa(nums[i]) + helper(arr, k - i * totalNums)
}
}
return ""
}更多相关文章
- 图解「剑指Offer」之旋转数组的最小数字
- 动画：面试必刷之找出数组中重复的数字
- 基于业务和平台理解数字营销概念
- C语言的一些练习以及自己写一个猜数字小游戏
- C语言的一些练习以及写一个猜数字游戏
- php用逗号格式化数字的方法（代码示例）
- PHP重置数组为连续数字索引的三种方式
- 分享一个匹配8-16位数字和字母密码的正则表达式
- php如何删除字符串中的重复数字或字符