Jamzen的技术博客
0%

LeetCode.排列序列

发表于 分类于 Valine：

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记, 当 n = 3 时, 所有排列如下：[ “123”,”132”,”213”,”231”,”312”,”321” ]。给定 n 和 k，返回第 k 个排列。

  • 示例 1：
    输入：n = 3, k = 3
    输出：”213”
  • 示例 2：
    输入：n = 4, k = 9
    输出：”2314”
  • 示例 3：
    输入：n = 3, k = 1
    输出：”123”
  1. 提示：
    1 <= n <= 9
    1 <= k <= n!

回溯&分治解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
object GetPermutation {

     def main(args: Array[String]): Unit = {
          println(getPermutation(7, 7))
          println(getPermutation(9, 233794))
          println(getPermutation(1, 1))
          println(getPermutation(2, 2))

          println(getPermutation1(7, 7))
          println(getPermutation1(1, 1))
          println(getPermutation1(2, 1))
          println(getPermutation1(2, 2))
          println(getPermutation1(3, 1))
          println(getPermutation1(3, 2))
          println(getPermutation1(3, 3))
          println(getPermutation1(3, 4))
          println(getPermutation1(3, 5))
          println(getPermutation1(3, 6))

          println(getPermutation1(9, 233794))
     }

     /**
      * 回溯法，时间复杂度O(k/n!)
      */
     def getPermutation(n: Int, k: Int): String = {
          val arr = new Array[Int](n)
          for (i <- 0 until n) {
               arr(i) = i + 1
          }

          val res = new ListBuffer[String]()
          backtrack(arr, new ListBuffer[Int](), res, k)
          res(k - 1)
     }

     def backtrack(nums: Array[Int], selected: ListBuffer[Int], res: ListBuffer[String], k: Int): Unit = {
          if (selected.length == nums.length) {
               res += selected.mkString("")
               return
          }

          for (num <- nums) {
               if (!selected.contains(num)) {
                    selected += num
                    backtrack(nums, selected, res, k)
                    if (res.length == k) {
                         return
                    } else {
                         selected -= num
                    }
               }
          }
     }

     def getPermutation1(n: Int, k: Int): String = {
          val arr = new Array[Int](n)
          for (j <- 1 to n) {
               arr(j - 1) = j
          }
          doGetPermutation(arr, k)
     }

     /**
      * 分治法，时间复杂度O(n^2)
      **/
     def doGetPermutation(nums: Array[Int], k: Int): String = {
          if (nums.length == 1 && k == 1) return nums(0).toString
          val k1 = jie(nums.length - 1)
          var ti = 0
          if (k > k1) {
               for (i <- 0 until nums.length) {
                    if (i * k1 < k && k <= (i + 1) * k1) {
                         ti = i
                    }
               }
          }
          nums(ti) + doGetPermutation(nums.filter(_ != nums(ti)), if (k <= k1) k else k - ti * k1)
     }

     def jie(k: Int): Int = {
          var res = 1
          for (i <- 1 until k + 1) {
               res *= i
          }
          res
     }

}