60.Permutation-Sequence

60. Permutation Sequence

题目地址

https://leetcode.com/problems/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:

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:

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

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

代码

Approach #1 Factorial Number System

class Solution {
  public String getPermutation(int n, int k) {
        int[] factorials = new int[n];
    List<Integer> nums = new ArrayList() {{ add(1);}};

    factorials[0] = 1;
    for (int i = 1; i < n; i++) {
      factorials[i] = factorials[i - 1] * i;
      nums.add(i + 1);
    }

    k--;

    StringBuilder sb = new StringBuilder();
    for (int i = n - 1; i > -1; i--) {
      int idx = k / factorials[i];
      k -= idx * factorials[i];

      sb.append(nums.get(idx));
      nums.remove(idx);
    }

    return sb.toString();
  }
}