首页 算法题解 LeetCode

原题链接：60. 排列序列
难度分类：Hard

# Problem

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

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

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

Examples

  • 示例 1：
    输入：n = 3, k = 3
    输出："213"

  • 示例 2：
    输入：n = 4, k = 9
    输出："2314"

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

# Approach

例如： n = 6, k = 373
初始化数组 remain = [1, 2, 3, 4, 5, 6] ;
首先应该明白，以 1 开头的全排列有 5! 个，以 2 开头的全排列有 5! 个 …… 共 5! ∗ 6 = 6! 个；

  1. 故 k = 373 时，全排列的第一个数字应该是 remain[k / 5!] = 4 ;
  2. 数组删除 4 , 此时 remain = [1, 2, 3, 5, 6] ; k = k % 5! = 12 ;
  3. 接下来就是在 remain 中找第 12 个全排列，重复 1，2 步即可 。

# Code

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> remain = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        
        k--;
        int x = 1;
        for(int i = 1; i <= n; i++) {
            x *= i;
            remain.add(i);
        }
        
        while(remain.size() > 0) {
            x /= (n--);
            int index = k / x;
            ans.add(remain.get(index));
            remain.remove(index);
            k %= x;
        }
        String ret = "";
        for(int i : ans) {
            ret += String.valueOf(i);
        }
        return ret;
    }
}