LeetCode60-第k个排列
这两天一直在做动态规划的题目
真的是做的头大啊
折磨的死去活来
却还得说:十分酸爽
你虐我千百遍,我还得待你如初恋
哎!!!
不过总算是有些心得了
敬请期待我的下一篇动态规划的文章
绝对有收获
对你要是没有帮助的话
请尽管来找我
我一定会。。。
会让你再看一遍的
哈哈哈哈哈哈哈哈哈
60-第k个排列
给出集合 [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"
思路:
本题对于python语言来说,有个很作弊的方法,就是直接用itertools.permutations()函数直接获取n个数值的所有组合情况,然后再取第k项即可。这个方法很简单,代码量也比较少,但是执行效率是极低,此处还是超出时间限制了,因为它就是暴力求解的。我也把这个代码给贴出来大家看看。
暴力法代码如下:
from itertools import permutations
class Solution:
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
n_list = list(range(1, n+1))
n_permutation = list(permutations(n_list, n))
if 0 < k <= len(n_permutation):
k_int_index = list(n_permutation[k-1])
k_str_index = map(str, k_int_index)
return ''.join(k_str_index)
else:
return []
if __name__ == "__main__":
n = 3
k = 3
final_result = Solution().getPermutation(n, k)
print(final_result)
既然暴力法行不通,那就只能是另辟蹊径了。当时就是想到,可不可以一项一项的确定每一位的数字,这样的话,随着确定的位数越来越多,我们需要考虑的情况也会越来越少的。答案是可以的,我当时总结的核心方法就是:通过后n-1项数的阶乘情况来确定第n项的数字,依次进行。
那如何来确定每一位上的数呢?我画了一张图大家可以先了解一下。
我按照这张图简要的说下,记当前位置为n,当前位置右面的总位数为m,给定n所对应的初始值列表为initial_list=list(range(1, n+1)),则n位置上面的值要用value[k] = k//m!来判断。这儿有个关键就是:组合的每个数里面是不可能有重复数值的,所以我们得要做好去重工作。我定义的initial_list列表就是用来干这个工作的,每次确定好一个位置上的数之后,要把该数从initial_list列表中去除掉,这个一定要注意了,否则结果会惨不忍睹。还有一些步骤我还没讲,具体的参考代码吧,我在那儿注释的比较清楚。
代码如下:
class Solution:
# 本题若采用暴力法直接将所有情况先列出来再求某一项,非常费时,而且是超出时间限制了
# 正确的方法应是:通过后n-1项数的阶乘情况来确定第n项的数字,依次进行
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
# 定义对应n个数字的顺序列表
initial_list = list(range(1, n+1))
# 保存临时结果-每一位的数字
current_answer = []
while k > 0:
# 通过k与后n-1项数的阶乘的商和余数来确定第n项的数字
indice_shang = k//self.jiecheng(n-1)
indice_mode = k % self.jiecheng(n-1)
# 如果余数为0,说明后n-1项数刚好整除,此时只需将后n-1项数逆序排列整合即可得到所需结果
if indice_mode == 0:
current_answer.append(initial_list[indice_shang-1])
initial_list.pop(indice_shang-1)
initial_list.sort(reverse=True)
current_answer.extend(initial_list)
# 如果余数为0,说明后n-1项数不能整除,得继续查找;但是此处与上面整除的情况不同的是第n项的数添加方法是不一样的
else:
current_answer.append(initial_list[indice_shang])
initial_list.pop(indice_shang)
# 上述操作每一次处理完,都得将n与k的值进行相应变化
k -= indice_shang*self.jiecheng(n-1)
n -= 1
final_answer = map(str, current_answer)
return "".join(final_answer)
# 求阶乘函数
def jiecheng(self, n):
if n == 0:
return 1
return n*self.jiecheng(n-1)
if __name__ == "__main__":
n = 5
k = 68
final_result = Solution().getPermutation(n, k)
print(final_result)
执行效率在80%左右,还算不错。