LeetCode Algorithm 0060 - Permutation Sequence (Medium)
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 and k , return the 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
已知集合 N 中有 n 个数字 {1,2,...,n} 一共有 n! 种序列。即,排列 Pnn 种序列。则:
-
第一位有 Pn1 种序列,其它位有 Pn−1n−1 种序列。即,每个数字有 Pn−1n−1 种序列。那么第 k 个序列第一位数字的位置 i1 为
i1=⌊(k−1)÷Pn−1n−1⌋
那么 取出 第一位数字 n1 为
n1=N[i1],取出后:N∩{n1}=ϕ
即,在第一位数字从 1 到 n−1 共有 n1−1 个 Pn−1n−1 序列。
之后到达第 k 个序列还需要 k1 个序列,即
k−1=k1(modPn−1n−1) -
同理,第二位数字的位置 i2 为
i2=⌊k1÷Pn−2n−2⌋
到达第 k 个序列还需要 k2 个序列,即
k1=k2(modPn−2n−2) -
最终,第 i 位数字的位置 i 为
i=⌊ki−1÷Pn−in−i⌋
到达第 k 个序列还需要 ki 个序列,即
ki−1=ki(modPn−in−i)
举例 n=5,k=8 ,则:
num | i | k−1=7 | N={1,2,3,4,5} | n=5 |
---|---|---|---|---|
1 | i1=⌊7÷4!⌋=0 | k1=7mod4!=7 | N={1,2,3,4,5} | n1=N[0]=1 |
2 | i2=⌊7÷3!⌋=1 | k2=7mod3!=1 | N={2,3,4,5} | n2=N[1]=3 |
3 | i3=⌊1÷2!⌋=0 | k3=1mod2!=1 | N={2,4,5} | n3=N[0]=2 |
4 | i4=⌊1÷1!⌋=1 | k4=1mod1!=0 | N={4,5} | n4=N[1]=5 |
5 | i5=⌊0÷0!⌋=0 | k5=0mod0!=0 | N={4} | n5=N[0]=4 |
则最终结果为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)
{
// 一共 n! 种序列
// 当第一位确定后,后面共有 (n-1)! 种序列
// 即,n个数有 n! = (n-1)! * n 种序列
// 则,第k个序列的第一位为 k / (n-1)! + 1
// 第二位是第 k % (n-1)! 个序列
// 然后求第二位 (n-2)!,以此类推
vector<int> nums;
for (int i = 1; i <= n; i++)
{
nums.push_back(i);
}
int fac = 1; // 求n-1的阶乘
for (int i = 2; i < n; i++)
{
fac *= i;
}
k--; // 数组从0开始
string seq;
int index;
for (int i = n - 1; i >= 0; i--)
{
index = k / fac; // k / (n-1)! + 1,下标和数值差1
seq.push_back(nums[index] + '0');
nums.erase(nums.begin() + index); // 删除已经使用的数字
k %= fac; // 求[n-1, n-2, ..., 1]个序列中的位置
if (i > 0)
{
fac /= i; // 求[(n-2)!, (n-3)!, ..., 0!]
}
}
return seq;
}
};
}