leetcode 60. 排列序列(困难、计数法)

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

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

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

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

示例1：

输入：n = 3, k = 3
输出：“213”

示例2：

输入：n = 4, k = 9
输出：“2314”

示例 3：

输入：n = 3, k = 1
输出：“123”

🧡 算法分析

此题方法之一是用库函数next_permutation

说明：next_permutation 是求当前排列的下一个排列。

方法二：计数法
算法分析：

1. 从高位到低位每一位分析；
2. 对于每一位，从小到大枚举未使用的数字，确定应当是几。

原理：
因为集合n个数的排列有n!个不同排列， 确定一个数后，后面应该有（n - 1)! 个不同排列，根据此性质，可定位到第几位数字是几。

举例：
当 n = 4, k = 14时：

首先我们将所有排列按首位分组后（就是固定第一位之后）：
1 + (2, 3, 4的全排列)
2 + (1, 3, 4的全排列)
3 + (1, 2, 4的全排列)
4 + (2, 3, 4的全排列)

接下来我们确定第 k=14个排列在哪一组中。每组的排列个数是 3!=6 个，所以第14个排列在第3组中，所以首位已经可以确定，是3。

然后我们再将第3组的排列继续分组：
31 + (2, 4的全排列)
32 + (1, 4的全排列)
34 + (1, 2的全排列)

接下来我们判断第 k=14个排列在哪个小组中。我们先求第 14个排列在第三组中排第几，由于前两组每组有6个排列，所以第14个排列在第3组排第 14−6∗2=2。
在第三组中每个小组的排列个数是 2!=2个，所以第 k 个排列在第1个小组，所以可以确定它的第二位数字是1。

依次类推，可以推出第14个排列是 3142。

💚 代码实现

方法一:

class Solution {
public:
    string getPermutation(int n, int k) {
        // 使用库函数
        string re;
        for(int i = 1; i <= n; i ++) re += to_string(i);
        for(int i = 0; i < k - 1; i ++)
            next_permutation(re.begin(), re.end());
      
        return re;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

方法二：

class Solution {
public:
    string getPermutation(int n, int k) {
        string re;
        vector<bool> st(n);
        for(int i = 0; i < n; i ++)
        {
            int f = 1;  // 预处理阶乘数字
            for(int j = 1; j < n - i; j ++) f *= j;
            for(int j = 0; j < n; j ++)
            {
                if(!st[j])
                {
                    if(k <= f)
                    {
                        re += to_string(j + 1);
                        st[j] = true;
                        break;
                    }
                    k -= f;
                }
            }
        }
        return re;
    }
};
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

执行结果：

💙 时间复杂度分析

方法一：
时间复杂度为：O(n! * k)

方法二：
时间复杂度为：两重循环，所以时间复杂度为O(n²)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习