Halo

A magic place for coding

0%

LeetCode解题报告（89）-- 60. Permutation Sequence

Posted on Edited on Valine:

Problem

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:

1
2
Input: n = 3, k = 3
Output: "213"

Example 2:

1
2
Input: n = 4, k = 9
Output: "2314"

Analysis

  题目与全排列有关，要求指定n和k，求出n的全排列中第k条排列的内容。如果把所有的排列都枚举出来再选第k个是不可能的，因为复杂度会非常高，而且需要很大的内存存储，所以思路只能是找一下有什么规律，直接利用k这个值去算出排列。

  我们以example2为例，分析一下如何算出来2314这个排列。假设所有的排列都被列了出来，实际上我们care的是他们的位置，数字排列的特点就是一旦高位确定下来，本身就会形成一个小组。这句话的意思是，对于2314来说，一旦确认了最高位是2 ，那么314这个组合的位置就是唯一的。基于这个规则，我们就从结果倒推，来看看314的位置是什么。以2开头之后，组合数量只有6个，314就是在六个里面排在第3个（下标为2）。然后进入下一个循环，确定以3开头之后，组合数量只有4个，14在四个里面排在第1个（下标为0）。继续进入下一个循环，确定以1 开头之后，就只剩下4了。

  看到上面的思路，可以知道有两个信息是很重要的：第一个信息是确定了高位之后，剩下组合数量。这个不难求出，数量就是剩下的数字的阶乘；第二个信息是在某个组里面的位置，这个位置的计算方式是：上一次排名对本组内组合数量取余的结果。继续用上面的例子解释，一开始的排名是9（下标为8），因为后面有3位，所以组内的组合数量是6。8 / 6 = 1，先确定位置的下标是1，所以就是数字2，选中了之后需要去除掉这个数字，后面不能再次使用，后续的数字往前靠。然后更新新的组内排名，所以是8 % 6 = 2，组内排名的下标就是2。进入下一位，因为数字后面有2位，所以组内的组合数是4。2 / 2 = 1 ，位置下标是1，所以就是数字3。然后更新新的组内排名，所以是2 % 2 = 0，组内排名的下标就是0。进入下一位，因为数字后面有1位，所以组内的组合数是1。0 / 1 = 0 ，位置下标就是0，所以就是数字1。然后更新组内排名，所以是0 % 1 = 0，组内排名的下标继续是0。进入下一位，因为是最后一个数字了，所以组合数为1。0 / 1 = 0，位置下标依然是0，所以就是数字4。到这里因为完成了四位数，所以任务就结束了。

Solution

  因为需要用到每个组的组合数量，可以提前计算好阶乘。然后用一个数组记录备用的数字，用完一个之后移除掉，以保持不会重复用到同一个数字。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        string num = "123456789";
        vector<int> f(n, 1);
        for (int i = 1; i < n; ++i) {
            f[i] = f[i - 1] * i;
        }
        k--;
        
        for (int i = n; i >= 1; --i) {
            int j = k / f[i - 1];
            k %= f[i - 1];
            res.push_back(num[j]);
            num.erase(j, 1);
        }
        return res;
    }
};

Summary

  在排列组合的题目里面，这道也算是比较经典的题目。这道题背后的知识是通过除法和取余来做分组排序，掌握这种思路能解决很多类似的题目。希望这篇博客能够帮助到您，感谢您的支持，欢迎转发、分享、评论，谢谢！

Welcome to my other publishing channels