60. Permutation Sequence
2022/1/2 6:08:23
本文主要是介绍60. Permutation Sequence,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Description
The set [1, 2, 3, ..., n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence.
Example
Input: n = 3, k = 3 Output: "213"
分析
刚开始决定采用 next permutation 进行求解。 考虑到 next permutation 通常分为 2 个部分,第一步是将某个数替换前面第一个小于它的数,第二部是进行刚替换过数字右边数字的排序。 考虑到排序比较耗时,在求第 kth 的排序时,时间复杂度会变成 k * n log n 。决定采用预先计算的方式进行优化,比如知道, [k1th, k2th, k3th ....] 对应的排列组合, 找到第一个小于 kth 的 kxth 排练组合,以此为基础进行计算。 想到这里,突然灵机一动。有了下面更好的优化 对于 n 个数的全排练 以 1 为开始数字的全排列有 (n-1) ! 以 2 为开始的有 (n-1)! ......... 假设 n 为 9, 现在计算 kth 开始的数字是以 5 为开始数字。 nkth 为 kth - 5 * 9 !。 新的数字组合从 [1,2,3,4, 6,7,8,9] , 以此类类推,计算 nkth 对应的组合数字!!
Tips
1 <= n <= 9 1 <= k <= n!
总结
这篇关于60. Permutation Sequence的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain