题目地址

https://leetcode-cn.com/problems/permutation-sequence/

题目描述

给出集合 [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"

题解

回溯算法

class Solution {
    private int targetK = 0;
    private String target = "";

    public String getPermutation(int n, int k) {
        targetK = k;
        boolean[] used = new boolean[n + 1];
        dfs(n, used, "");
        return target;
    }

    public void dfs(int n, boolean[] used, String permutation) {
        if (permutation.length() == n) {
            targetK--;
            if (targetK == 0) {
                target = permutation;
            }
            return;
        }
        for (int i = 1; i <= n; ++ i) {
            // 过滤已选择的
            if (used[i]) continue;

            // 做选择
            used[i] = true;
            
            dfs(n, used, permutation + i);
            
            // 撤销选择
            used[i] = false;
        }
    }
}

数学计算

对于 n 位数的排列，第一位数固定的情况下，后面的看成是 n-1 位数的排列。
因此以 1, 2, 3, ..., n 中一个数开头的排列有 (n-1)! 个。

• （1）假设 range = (n-1)!，那么有：
  • 以 1 开头的排列占据 0 ~ range-1
  • 以 2 开头的排列占据 range ~ (2*range)-1
  • 以 3 开头的排列占据 2*range ~ (3*range)-1
  • ...
  • 以 n 开头的排列占据 (n-1)*range ~ (n*range)-1
• （2）因为数组下标从 0 开始，所以用 index = k / range 就可以选出第一位的数字是什么。
• （3）k -= (index * range)，从第（1）步开始轮询即可。

• 使用 String 拼接字符串

class Solution {
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; ++ i) {
            nums[i] = i + 1;
        }

        return getPermutation(nums, k);
    }

    public String getPermutation(int[] nums, int k) {
        String permutation = "";

        int n = nums.length;
        for (int i = 0; i < n; ++ i) {
            int range = factorial(n - i - 1);
            int index = getIndex(k, range);
            
            permutation += nums[index];

            k -= (index * range);
            nums[index] = Integer.MAX_VALUE;
            Arrays.sort(nums);
        }

        return permutation;
    }

    public int getIndex(int k, int range) {
        int index = k / range;
        if (k % range == 0) {
            index = index - 1;
        }
        return index;
    }

    public int factorial(int n) {
        int result = 1;
        for (int i = 2; i <= n; ++ i) {
            result *= i;
        }
        return result;
    }
}

• 使用 StringBuilder 拼接字符串

class Solution {
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; ++ i) {
            nums[i] = i + 1;
        }

        return getPermutation(nums, k);
    }

    public String getPermutation(int[] nums, int k) {
        StringBuilder permutation = new StringBuilder(); // 变更

        int n = nums.length;
        for (int i = 0; i < n; ++ i) {
            int range = factorial(n - i - 1);
            int index = getIndex(k, range);
            
            permutation.append(nums[index]); // 变更

            k -= (index * range);
            nums[index] = Integer.MAX_VALUE;
            Arrays.sort(nums);
        }

        return permutation.toString(); // 变更
    }

    public int getIndex(int k, int range) {
        int index = k / range;
        if (k % range == 0) {
            index = index - 1;
        }
        return index;
    }

    public int factorial(int n) {
        int result = 1;
        for (int i = 2; i <= n; ++ i) {
            result *= i;
        }
        return result;
    }
}