题目描述:Leetcode 0060 排列序列
分析
-
本题的考点:数学。
-
对于c++而言,可以使用next_permutation,计算量为 n ! × n n! times n n!×n,最大为 9 ! × 9 = 3 , 265 , 920 9! times 9 = 3,265,920 9!×9=3,265,920,可以通过,考试肯定用这种做法。
-
下面讲解另一种做法:计数法。
-
对于n,我们要求第k大的小的数,我们可以依次考虑1~n这些位置应该放入哪个数字,从第一个位置开始考虑,如果放入1的话,则后面还有n-1个位置,一共有(n-1)!种方案,比较k和(n-1)!的大小,如果k > (n-1)!,说明第k小的数必定不可能是1开头的数字。之后将k更新为k-(n-1)!,考虑第一个位置放入2,直到找到第一个位置放置的数字,使得 k ≤ ( n − 1 ) ! k le (n-1)! k≤(n−1)!,则该数字就是第一位应该放的数字。
-
依次考虑后面2~n位应该放入哪些数字。注意已经用过的数字不能再使用,需要使用一个数组st进行判重。
-
如下图,是n=4, k=10对应的情况:
代码
- C++
class Solution { public: string getPermutation(int n, int k) { string res; for (int i = 1; i <= n; i++) res += to_string(i); for (int i = 0; i < k - 1; i++) { next_permutation(res.begin(), res.end()); } return res; } };
class Solution { public: string getPermutation(int n, int k) { vectorfact(10, 1); // 阶乘 for (int i = 2; i < 10; i++) fact[i] = fact[i - 1] * i; string res; vector st(10); // 判重数组 for (int i = 0; i < n; i++) // 枚举每个位置, 即res[i]应该填入哪个数字 for (int j = 1; j <= n; j++) // 枚举所有数字 if (!st[j]) { // j还没被使用过 if (fact[n - 1 - i] < k) // 说明res[i]不应该放入j k -= fact[n - 1 - i]; else { res += to_string(j); st[j] = true; break; // 表示res[i]已经填入了正确的数字 } } return res; } };
- Java
class Solution { public String getPermutation(int n, int k) { int[] fact = new int[n]; fact[0] = 1; for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i; StringBuilder sb = new StringBuilder(); boolean[] st = new boolean[10]; for (int i = 0; i < n; i++) for (int j = 1; j <= n; j++) if (!st[j]) { if (fact[n - 1 - i] < k) k -= fact[n - 1 - i]; else { sb.append((char)('0' + j)); st[j] = true; break; } } return sb.toString(); } }
- Python
class Solution: def getPermutation(self, n: int, k: int) -> str: fact = [1 for _ in range(n)] for i in range(1, n): fact[i] = fact[i - 1] * i res = "" st = [False for _ in range(10)] for i in range(n): for j in range(1, n + 1): if not st[j]: if fact[n - 1 - i] < k: k -= fact[n - 1 - i] else: res += chr(j + ord('0')) st[j] = True break return res
时空复杂度分析
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)。计数法中有两重循环。
- 空间复杂度: O ( n ) O(n) O(n)。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)