leetcode_60. 排列序列

60. 排列序列

题目描述：给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

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

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3
输出："213"

示例 2：

输入：n = 4, k = 9
输出："2314"

示例 3：

输入：n = 3, k = 1
输出："123"

提示：

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

 回溯思路：

        创建 sequence 列表用来保存所有生成的排列； temp 列表用来保存当前正在构建的排列；used 数组来标记每个数字是否已经被使用。

• 如果当前数字没有被使用过(!used[i]),则将其添加到 temp 列表中,并标记为已使用(used[i] = true)。
• 递归调用 backTrack 函数继续生成排列。
• 在回溯过程中,将最后添加的数字从 temp 列表中移除,并标记为未使用(used[i] = false)。

class Solution {List<List<Integer>> sequence = new ArrayList<>();List<Integer> temp = new ArrayList<>();public String getPermutation(int n, int k) {boolean[] used = new boolean[n + 1];backTrack(used, n, k);StringBuilder sb = new StringBuilder();for (int num : sequence.get(k - 1)) {sb.append(num);}return sb.toString();}public void backTrack(boolean[] used, int n, int k) {if (temp.size() == n) {sequence.add(new ArrayList<>(temp));}for (int i = 1; i < n + 1; i++) {if (sequence.size() == k) {return;}if (!used[i]) {temp.add(i);used[i] = true;backTrack(used, n, k);temp.remove(temp.size() - 1);used[i] = false;}}}
}

代码思路：利用数学规律将全排列问题转化为一系列的子问题求解。通过不断缩小问题规模,最终确定出第 k 个排列：

1. 首先利用数学规律,计算出 n 的全排列总共有多少个。这个数量就是 n! 个。
2. 根据 k 的值,确定第 k 个排列应该从哪一个数字开始。这是通过计算 k/(n-1)! 得到。
3. 确定了第一个数字之后,剩下的问题就变成了在剩余的 n-1 个数字中找到第 k % (n-1)! 个排列。
4. 依次确定每一位数字。每确定一位,就从候选集中移除该数字,减少问题的规模。

class Solution {public String getPermutation(int n, int k) {StringBuilder sb = new StringBuilder();List<Integer> nums = new ArrayList<>();int[] factorial = new int[n + 1];factorial[0] = 1;for (int i = 0; i < n; i++) {nums.add(i + 1);}for (int i = 1; i < n + 1; i++) {factorial[i] = factorial[i - 1] * i;}k--;for (int i = n - 1; i >= 0; i--) {int index = k / factorial[i];sb.append(nums.remove(index));k -= index * factorial[i];}return sb.toString();}
}