60. Permutation Sequence.md

60. Permutation Sequence

---

leetcode Daily Challenge on June 20th, 2020

leetcode-cn Daily Challenge on September 5th, 2020

---

Difficulty : Hard

Related Topics : Math、Backtracking

---

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 k^th 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"

---

Solution

• mine
  • Java
    • Math Runtime: 1 ms, faster than 98.52%, Memory Usage: 36.9 MB, less than 78.08% of Java online submissions

      // O(N)time O(N)space
      public String getPermutation(int n, int k) {
          List<Integer> list = new ArrayList<>();
          int res = 1;
          for (int i = 1; i <= n; i++) {
              list.add(i);
              res *= i;
          }
          StringBuilder sb = new StringBuilder();
          int i = 0;
          while (k != 0) {
              res /= (n - i);
              i++;
              sb.append(list.remove((k - 1) / res));
              k = k % res;
          }
          while (list.size() > 0) {
              sb.append(list.remove(list.size() - 1));
          }
          return sb.toString();
      }
      

---

• the most votes

• Runtime: 1 ms, faster than 98.52%, Memory Usage: 36.8 MB, less than 86.90% of Java online submissions

  // O(N)time O(N)space
  public String getPermutation(int n, int k) {
      StringBuilder sb = new StringBuilder();
      ArrayList<Integer> num = new ArrayList<Integer>();
      int fact = 1;
      for (int i = 1; i <= n; i++) {
          fact *= i;
          num.add(i);
      }
      for (int i = 0, l = k - 1; i < n; i++) {
          fact /= (n - i);
          int index = (l / fact);
          sb.append(num.remove(index));
          l -= index * fact;
      }
      return sb.toString();
  }
  

---