当前位置:网站首页>LeetCode Algorithm 0060 - Permutation Sequence (Medium)
LeetCode Algorithm 0060 - Permutation Sequence (Medium)
2020-11-13 00:31:02 【Sandy rabbit】
LeetCode Algorithm 0060 - Permutation Sequence (Medium)
Return to category : All articles >> Basic knowledge of
Return to the superior :LeetCode Algorithm catalog
Problem Link: https://leetcode.com/problems/permutation-sequence/
Related Topics: Math
Backtracking
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:
-
1,
"123"
-
2,
"132"
-
3,
"213"
-
4,
"231"
-
5,
"312"
-
6,
"321"
Given n n n and k k k , return the k t h k^{th} kth permutation sequence.
Note:
-
Given n will be between 1 and 9 inclusive.
-
Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Analysis
Known set N N N There is n n n A digital { 1 , 2 , . . . , n } \{1,2,...,n\} { 1,2,...,n} Altogether n ! n! n! A sequence of . namely , array P n n P_n^n Pnn A sequence of . be :
-
The first one has P n 1 P_n^1 Pn1 A sequence of , Others have P n − 1 n − 1 P_{n-1}^{n-1} Pn−1n−1 A sequence of . namely , Each number has P n − 1 n − 1 P_{n-1}^{n-1} Pn−1n−1 A sequence of . So the first k k k The position of the first digit in a sequence i 1 i_1 i1 by
i 1 = ⌊ ( k − 1 ) ÷ P n − 1 n − 1 ⌋ i_1 = \lfloor (k-1) \div P_{n-1}^{n-1} \rfloor i1=⌊(k−1)÷Pn−1n−1⌋
that Take out First digit n 1 n_1 n1 by
n 1 = N [ i 1 ] , After taking it out : N ∩ { n 1 } = ϕ n_1 = N \left[ i_1 \right], \quad \text{ After taking it out :} N \cap \{ n_1 \} = \phi n1=N[i1], After taking it out :N∩{ n1}=ϕ
namely , In the first digit from 1 1 1 To n − 1 n-1 n−1 share n 1 − 1 n_1-1 n1−1 individual P n − 1 n − 1 P_{n-1}^{n-1} Pn−1n−1 Sequence .
Then arrive at the k k k A sequence also needs k 1 k_1 k1 A sequence of , namely
k − 1 = k 1 ( m o d    P n − 1 n − 1 ) k-1 = k_1 (mod \; P_{n-1}^{n-1}) k−1=k1(modPn−1n−1) -
Empathy , The position of the second digit i 2 i_2 i2 by
i 2 = ⌊ k 1 ÷ P n − 2 n − 2 ⌋ i_2 = \lfloor k_1 \div P_{n-2}^{n-2} \rfloor i2=⌊k1÷Pn−2n−2⌋
Arrive at k k k A sequence also needs k 2 k_2 k2 A sequence of , namely
k 1 = k 2 ( m o d    P n − 2 n − 2 ) k_1 = k_2 (mod \; P_{n-2}^{n-2}) k1=k2(modPn−2n−2) -
Final , The first i i i The position of the digit i i i by
i = ⌊ k i − 1 ÷ P n − i n − i ⌋ i = \lfloor k_{i-1} \div P_{n-i}^{n-i} \rfloor i=⌊ki−1÷Pn−in−i⌋
Arrive at k k k A sequence also needs k i k_i ki A sequence of , namely
k i − 1 = k i ( m o d    P n − i n − i ) k_{i-1} = k_i (mod \; P_{n-i}^{n-i}) ki−1=ki(modPn−in−i)
give an example n = 5 , k = 8 n=5, k=8 n=5,k=8 , be :
num | i i i | k − 1 = 7 k-1=7 k−1=7 | N = { 1 , 2 , 3 , 4 , 5 } N = \{ 1, 2, 3, 4, 5 \} N={ 1,2,3,4,5} | n = 5 n=5 n=5 |
---|---|---|---|---|
1 | i 1 = ⌊ 7 ÷ 4 ! ⌋ = 0 i_1 = \lfloor 7 \div 4! \rfloor = 0 i1=⌊7÷4!⌋=0 | k 1 = 7   m o d   4 ! = 7 k_1 = 7 \, mod \, 4! = 7 k1=7mod4!=7 | N = { 1 , 2 , 3 , 4 , 5 } N = \{ 1, 2, 3, 4, 5 \} N={ 1,2,3,4,5} | n 1 = N [ 0 ] = 1 n_1 = N[0] = 1 n1=N[0]=1 |
2 | i 2 = ⌊ 7 ÷ 3 ! ⌋ = 1 i_2 = \lfloor 7 \div 3! \rfloor = 1 i2=⌊7÷3!⌋=1 | k 2 = 7   m o d   3 ! = 1 k_2 = 7 \, mod \, 3! = 1 k2=7mod3!=1 | N = { 2 , 3 , 4 , 5 } N = \{ 2, 3, 4, 5 \} N={ 2,3,4,5} | n 2 = N [ 1 ] = 3 n_2 = N[1] = 3 n2=N[1]=3 |
3 | i 3 = ⌊ 1 ÷ 2 ! ⌋ = 0 i_3 = \lfloor 1 \div 2! \rfloor = 0 i3=⌊1÷2!⌋=0 | k 3 = 1   m o d   2 ! = 1 k_3 = 1 \, mod \, 2! = 1 k3=1mod2!=1 | N = { 2 , 4 , 5 } N = \{ 2, 4, 5 \} N={ 2,4,5} | n 3 = N [ 0 ] = 2 n_3 = N[0] = 2 n3=N[0]=2 |
4 | i 4 = ⌊ 1 ÷ 1 ! ⌋ = 1 i_4 = \lfloor 1 \div 1! \rfloor = 1 i4=⌊1÷1!⌋=1 | k 4 = 1   m o d   1 ! = 0 k_4 = 1 \, mod \, 1! = 0 k4=1mod1!=0 | N = { 4 , 5 } N = \{ 4, 5 \} N={ 4,5} | n 4 = N [ 1 ] = 5 n_4 = N[1] = 5 n4=N[1]=5 |
5 | i 5 = ⌊ 0 ÷ 0 ! ⌋ = 0 i_5 = \lfloor 0 \div 0! \rfloor = 0 i5=⌊0÷0!⌋=0 | k 5 = 0   m o d   0 ! = 0 k_5 = 0 \, mod \, 0! = 0 k5=0mod0!=0 | N = { 4 } N = \{ 4 \} N={ 4} | n 5 = N [ 0 ] = 4 n_5 = N[0] = 4 n5=N[0]=4 |
The final result is 13254.
Solution C++
// Author: https://blog.csdn.net/DarkRabbit
// Problem: https://leetcode.com/problems/permutation-sequence/
// Difficulty: Medium
// Related Topics: `Math` `Backtracking`
#pragma once
#include "pch.h"
namespace P60PermutationSequence
{
class Solution
{
public:
string getPermutation(int n, int k)
{
// altogether n! A sequence of
// When the first one is confirmed , There is... In the back (n-1)! A sequence of
// namely ,n The number is n! = (n-1)! * n A sequence of
// be , The first k The first digit of a sequence is k / (n-1)! + 1
// The second is the k % (n-1)! A sequence of
// Then ask for the second place (n-2)!, And so on
vector<int> nums;
for (int i = 1; i <= n; i++)
{
nums.push_back(i);
}
int fac = 1; // seek n-1 The factorial
for (int i = 2; i < n; i++)
{
fac *= i;
}
k--; // Array from 0 Start
string seq;
int index;
for (int i = n - 1; i >= 0; i--)
{
index = k / fac; // k / (n-1)! + 1, Difference between subscript and value 1
seq.push_back(nums[index] + '0');
nums.erase(nums.begin() + index); // Delete numbers that have been used
k %= fac; // seek [n-1, n-2, ..., 1] Position in sequence
if (i > 0)
{
fac /= i; // seek [(n-2)!, (n-3)!, ..., 0!]
}
}
return seq;
}
};
}
版权声明
本文为[Sandy rabbit]所创,转载请带上原文链接,感谢
边栏推荐
- OPTIMIZER_TRACE详解
- 使用Consul实现服务发现:instance-id自定义
- OPTIMIZER_ Trace details
- Using consult to realize service discovery: instance ID customization
- Summary of common string algorithms
- Summary of common algorithms of linked list
- Linked blocking Queue Analysis of blocking queue
- 构建者模式(Builder pattern)
- Builder pattern
- Newbe.ObjectVisitor 样例 1
猜你喜欢
-
Newbe.ObjectVisitor Example 1
-
Farewell to runaway
-
LeetCode Algorithm 0060 - Permutation Sequence (Medium)
-
编程基础 - 栈的应用 - 混洗(Stack Shuffling)
-
Fundamentals of programming stack shuffling
-
【色卡】常用色谱简析,中国传统颜色卡,代码附RBG,HC
-
[color card] brief analysis of commonly used chromatograms, Chinese traditional color cards, code with RBG, HC
-
MongoDB 副本集之入门篇
-
Introduction to mongodb replica set
-
My name is mongodb, don't understand me. After reading my story, you will get started!
随机推荐
- roboguide破解安装教程
- Roboguide cracking installation tutorial
- The transformation of town street intelligent street lamp under the industrial intelligent gateway
- Remote smoke monitoring of environmental protection data acquisition instrument under Internet of things
- JS实现鼠标移入DIV随机变换颜色
- Flutter 页面中的异常处理ErrorWidget
- Exception handling errorwidget in fluent page
- Bolt's practice of route management of flutter (page decoupling, process control, function expansion, etc.)
- C语言系统化精讲 重塑你的编程思想 打造坚实的开发基础
- Skywalking系列博客6-手把手教你编写Skywalking插件
- Skywalking series blog 7 - dynamic configuration
- Skywalking series blog 6 - help you write skywalking plug-in
- 博客主机_自动申请续期免费证书
- Blog host_ Automatic renewal of free certificate
- 0x05 - 综合示例,导出 CSV
- 0x05 - synthesis example, export to CSV
- 0x02 - create and cache object visitors
- flutter圆形或线型进度条
- flutter给滚动内容添加粘性header组件
- Fluent round or linear progress bar
- Fluent adds sticky header components to scrolling content
- Typora uses latex to insert mathematical formulas
- 配电自动化终端dtu
- How to write a thesis opening report
- 基于C的PHP快速IP解析扩展,IP检测
- Based on C PHP fast IP resolution extension, IP detection
- 点击平滑滚动效果
- Click smooth scrolling effect
- HighGo Database触发器使用案例(APP)
- Use case of highgo database trigger (APP)
- ES6之Map对象
- Flutter 最常出现的错误
- Flutter's most common mistakes
- 捕获 flutter app的崩溃日志并上报
- Capture and report the crash log of the flutter app
- SQL Server递归查询在Highgo DB中实现 (APP)
- Implementation of SQL Server recursive query in highgo dB (APP)
- 关于browserslist配置项
- About browserlist configuration items
- FTK1000使用视频一招搞定多模光损耗