Sitch's Blog
0%

LeetCode-No-60

发表于 分类于 Valine：

第K个排列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123" "132" "213" "231" "312" "321" 给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。 给定 k 的范围是[1,  n!]。

示例 1:

输入: n = 3, k = 3 输出: "213"

示例 2:

输入: n = 4, k = 9 输出: "2314"

题目分析

  1. 我一开始想到的是全排列的函数的复用，我能找到全排列难道我找不到第k个排列？但我发现全排列那里并没有按序排列，因此不可复用..

  2. 可以复用 下一个排列 的函数，毕竟一直找找到第K个就好，效率较低，没尝试。

  3. 数学计算。全排列每个位置的每个数其实是有数学特征的。比如对 1 2 3

    3.1 首位情况： 肯定先是1在首位两次，然后是2首位2次，然后是3首位两次。

    3.2 次位情况：除掉首位数字，剩下的数字在nums[]中，同样也是先nums[0]作为次位，出现 尾部排列次数 次，然后是nums[1]...依次类推。

    综上：即我们知道每位的次数情况，比如 1 2 3中，我们要找第5个排列，因为首位1在前两个， 首位2 在3 4 个，因此 第5个排列必然是首位3。 再看次位，第5个排列，除去 1 2 首位的四个，我们要找的是3首位的第一个，依次类推即可。 即我们可以直接计算出每一位应该是什么数字。然后组成result即可。

  4. 细节

    4.1 当前位 每个数字出现次数，由尾部的全排列次数决定，而全排列是n！，因此最好能预置个阶乘结果数组。

    4.2 k/fac[n-1] 向上取整得i，此时该位应该是 nums里的第i个数（下标i-1），同时对nums删除这个数。

    4.3 n==1 时，nums只剩一个数，直接连上并返回。

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    string getPermutation(int n, int k) 
    {   
        //题解数组
        const vector<int fac = {0,1,2,6,24,120,720,5040,40320,362880,3628800};
        string result(n,'0');
        string nums(n,'0');
        for(int i=0;i<n;i++)
            nums[i]='1'+i;
        
        for(int i=0;n0;i++)
        {   
            int a;
            int left=0;
            if(n=2) //计算每个首位有多少个排列,跳过这些排列
            {   
                left=fac[n-1];
                a=k/left;
                if(k%left!=0)
                    a++;
                result[i]=nums[a-1];
                k-=(a-1)*left;
                nums.erase(a-1,1);
                n--;

            }
            else //只剩一个数,直接修改返回
            {
                result[i]=nums[0];
                return result;   
            }

        }
        return result;
    }
 
    
};