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$ and $k$ , return the $k^{th}$ 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$ There is $n$ A digital { 1 , 2 , . . . , n } \{1,2,...,n\} { 1,2,...,n} Altogether $n!$ A sequence of . namely , array $P_n^n$ A sequence of . be ：

• The first one has $P_n^1$ A sequence of , Others have $P_{n-1}^{n-1}$ A sequence of . namely , Each number has $P_{n-1}^{n-1}$ A sequence of . So the first $k$ The position of the first digit in a sequence $i_1$ by
  $$i_1=\lfloor (k-1)÷P_{n-1}^{n-1}\rfloor$$
  that Take out First digit $n_1$ 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$ To $n-1$ share $n_1-1$ individual $P_{n-1}^{n-1}$ Sequence .
  Then arrive at the $k$ A sequence also needs $k_1$ A sequence of , namely
  $$k-1=k_1(mod{P}_{n-1}^{n-1})$$

• Empathy , The position of the second digit $i_2$ by
  $$i_2=\lfloor k_1÷P_{n-2}^{n-2}\rfloor$$
  Arrive at $k$ A sequence also needs $k_2$ A sequence of , namely
  $$k_1=k_2(mod{P}_{n-2}^{n-2})$$

• Final , The first $i$ The position of the digit $i$ by
  $$i=\lfloor k_{i-1}÷P_{n-i}^{n-i}\rfloor$$
  Arrive at $k$ A sequence also needs $k_i$ A sequence of , namely
  $$k_{i-1}=k_i(mod{P}_{n-i}^{n-i})$$

give an example $n=5,k=8$ , be ：

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;
        }

    };
}