当前位置:网站首页>LeetCode Algorithm 0060 - Permutation Sequence (Medium)

LeetCode Algorithm 0060 - Permutation Sequence (Medium)

2020-11-13 00:31:02 沙沙的兔子

LeetCode Algorithm 0060 - Permutation Sequence (Medium)

返回分类:全部文章 >> 基础知识

返回上级:LeetCode 算法目录


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

已知集合 N N N 中有 n n n 个数字 { 1 , 2 , . . . , n } \{1,2,...,n\} { 1,2,...,n} 一共有 n ! n! n! 种序列。即,排列 P n n P_n^n Pnn 种序列。则:

  • 第一位有 P n 1 P_n^1 Pn1 种序列,其它位有 P n − 1 n − 1 P_{n-1}^{n-1} Pn1n1 种序列。即,每个数字有 P n − 1 n − 1 P_{n-1}^{n-1} Pn1n1 种序列。那么第 k k k 个序列第一位数字的位置 i 1 i_1 i1
    i 1 = ⌊ ( k − 1 ) ÷ P n − 1 n − 1 ⌋ i_1 = \lfloor (k-1) \div P_{n-1}^{n-1} \rfloor i1=(k1)÷Pn1n1
    那么 取出 第一位数字 n 1 n_1 n1
    n 1 = N [ i 1 ] , 取出后: N ∩ { n 1 } = ϕ n_1 = N \left[ i_1 \right], \quad \text{取出后:} N \cap \{ n_1 \} = \phi n1=N[i1],取出后:N{ n1}=ϕ
    即,在第一位数字从 1 1 1 n − 1 n-1 n1 共有 n 1 − 1 n_1-1 n11 P n − 1 n − 1 P_{n-1}^{n-1} Pn1n1 序列。
    之后到达第 k k k 个序列还需要 k 1 k_1 k1 个序列,即
    k − 1 = k 1 ( m o d    P n − 1 n − 1 ) k-1 = k_1 (mod \; P_{n-1}^{n-1}) k1=k1(modPn1n1)

  • 同理,第二位数字的位置 i 2 i_2 i2
    i 2 = ⌊ k 1 ÷ P n − 2 n − 2 ⌋ i_2 = \lfloor k_1 \div P_{n-2}^{n-2} \rfloor i2=k1÷Pn2n2
    到达第 k k k 个序列还需要 k 2 k_2 k2 个序列,即
    k 1 = k 2 ( m o d    P n − 2 n − 2 ) k_1 = k_2 (mod \; P_{n-2}^{n-2}) k1=k2(modPn2n2)

  • 最终,第 i i i 位数字的位置 i i i
    i = ⌊ k i − 1 ÷ P n − i n − i ⌋ i = \lfloor k_{i-1} \div P_{n-i}^{n-i} \rfloor i=ki1÷Pnini
    到达第 k k k 个序列还需要 k i k_i ki 个序列,即
    k i − 1 = k i ( m o d    P n − i n − i ) k_{i-1} = k_i (mod \; P_{n-i}^{n-i}) ki1=ki(modPnini)

举例 n = 5 , k = 8 n=5, k=8 n=5,k=8 ,则:

num i i i k − 1 = 7 k-1=7 k1=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

则最终结果为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;
        }

    };
}

版权声明
本文为[沙沙的兔子]所创,转载请带上原文链接,感谢
https://blog.csdn.net/darkrabbit/article/details/89735280

随机推荐