LeetCode - Permutation Sequence

Problem description

description

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"
  

Analysis

Basically, we can use the sequence of the permutation to solve this problem, let’s use example 1, we can know there are 2 permutations for the case which has 1 in the first number, so if we have k = 3, then the first number is 2, if k = 5, then first number is 3.

Here’s the code:

public String getPermutation(int n, int k) {
    int cycle = 1;
    int i = 1;

    for (; i < n; i++) {
      cycle *= i;
    }
    i--;

    List<Integer> vals = new ArrayList<>();

    for (int j = 1; j <= n; j++) {
      vals.add(j);
    }

    StringBuilder sb = new StringBuilder();

    while (k != 0 && i != 0) {
      int next = 0;
      while (k > cycle) {
        next++;
        k -= cycle;
      }

      sb.append(vals.get(next));
      vals.remove(next);

      cycle /= i;
      i--;
    }

    sb.append(vals.get(0));

    return sb.toString();
  }

What to improve

• be careful about the boundary.