LeetCode60. 第k个排列

LeetCode60. 第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”

题目解析

一般这种情况，需要将例子扩大范围，从而找到更多更明显的规律。一开始和参考博客的想法是差不多的，但是是直接寻找K值，而参考博客的做法是将K值减一，其实差不多，只是不需要多些处理。我们这里用例子 n=4,k=15为例。 首先，列出所有情况： 1234 1243 1324 1342 1423 1432 /******* 2134 2143 2314 2341 2413 2431 /******* 3124 3142 3214 --> here 3241 3412 3421 /******* 4123 4132 4213 4231 4312 4321 可以看到，首先第一位是按照 (n-1)!=(4-1)!=6个分组长度来区分，然后第二位是按照(3-1)!=2的分组长度区分，因此我们先定义一个存放 0-(n-1)阶乘结果的数组[1,1,2,6…]。这里我们先将k-1得到14。然后定义我们需要定位的数组"123456789"（下标从0开始）。按照这个例子，定位数组是"1234"

计算 14/3! = 2 余 2，其中结果2是结果在最高位的定位，找到定位数组下标为2的数字，为3，存入结果数组 3。下一次定位时已经不包含这个数，因此我们需要将其在定位数组中去除。得到新的定位数组"124"。余数2则是其在以3开头的分组中的位置（下标0开始）。但是我们无法直接取到这个数，所以继续推。我们可以看到接下来可以按照2个来进行分组，也即(3-1)!=2，存入结果数组 32。这里有一个技巧点，就是要利用余数来除以新的分组长度。也即上一步得到的 2/2! =1 余 0，其中得到的结果1是其在新的最高位的定位，也即"124"中的2，所以第二位数是2。得到新的定位数组"14"。按照这个规律，余数 0/1! = 0 余 0，得到的结果，在最高位的位置为0，也即为"1"。存入结果数组 321。得到新的定位数组"4"。余数 0/0! = 0 余 0，得到结果在新的最高位的位置为0，也即"4"存入结果数组 3214。综上，得到最终的结果 3214。

代码

class Solution { public: string getPermutation(int n, int k) { string res; string num = "123456789"; vector<int> f(n, 1); // 数组f下标从中存放 0-(n-1)阶乘结果 for (int i = 1; i < n; ++i) { f[i] = f[i - 1] * i; // 1,2,6... } k--; // 将寻找的第k个排列转换为数组下标 for (int i = n; i >= 1; --i) { //循环将1-n的每个数取出 int j = k / f[i - 1]; k %= f[i - 1]; res.push_back(num[j]); num.erase(j, 1); // erase(pos,n); 删除从pos开始的n个字符,从0开始计数 } return res; } };

参考：https://www.cnblogs.com/grandyang/p/4358678.html