0%

[Leetcode]60. Permutation Sequence(C++)

题目描述

题目链接:60. Permutation Sequence

Given n and k, return the kth permutation sequence.

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"

例子

例子 1

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

例子 2

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

例子 3

Input: n = 3, k = 1
Output: "123"

Constraints

  • 1 <= n <= 9
  • 1 <= k <= n!

解题思路

在题目中给出的例子中可以发现,对于 n = 3 的所有情况,可以按照首元素 123 均等的分为 3 组,每一组中有 (n - 1)! 个。以此我们可以发现一个规律,对于 n 个数字的排列情况来说,它的所有排列可以分为 n 组,每组中有 (n - 1)! 个子排列。我们要求第 k 个的话,第一步可以首先用 k / (n - 1)! 就知道我们要求的排列落在哪一个组中,在对于该组中我们递归的用 k = k % (n - 1)!, n = n - 1 进行重复计算即可,终止情况是 n = 1 此时只有一种排列即该数字本身。具体操作过程中,由于每次循环我们都会用掉一个元素,所以需要在该序列中,把那个数字去掉。

代码如下:

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
#include <string>
#include <vector>

class Solution {
public:
std::string getPermutation(int n, int k) {
std::vector<int> nums;
std::vector<int> factorial(10, 1);
for (int i = 1; i <= 9; i++) {
nums.push_back(i);
factorial[i] = factorial[i - 1] * i;
}

std::string perm = "";
k--;
while (n > 0) {
int select = k / factorial[n - 1];
k %= factorial[n - 1];

perm += '0' + nums[select];
for (int i = select; i < nums.size() - 1; ++i) {
nums[i] = nums[i + 1];
}

n--;
}

return perm;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 60.PermutationSequence.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions