Lexicographically n-th Permutation of a String in Java

给定一个仅由小写字母组成的长度为 m 的字符串。我们必须使用字典序方法来确定该字符串的第 n 个排列。

示例 1

输入

字符串 str[] = "xyz"

int n = 4

输出

字典序排列为 "xzy"

解释

所有可能排列的排序顺序

xyz, xzy, yxz, yzx, zxy, zyx。第 4 个排列是 "xzy"。

示例 2

输入

字符串 str[] = "abcd"

int n = 10

输出

字典序排列为 "bdac"

解释

所有可能排列的排序顺序

abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bdac, ..... 第 10 个排列是 "bdac"。

示例 3

输入

字符串 str[] = "mn"

int n = 2

输出

字典序排列为 "nm"

解释

所有可能排列的排序顺序

mn, nm。第 2 个排列是 "nm"。

方法：使用 STL 生成给定字符串的排列

使用 STL 打印第 n 个排列的概念相对容易理解。我们应该使用 STL 来获取下一个排列，并一直持续直到我们达到第 n 个排列。我们在第 n 次迭代后退出循环，并打印包含我们第 n 个排列的字符串。

算法

步骤 1：创建一个字符串 s 和一个 整数 N。

步骤 2：将字符串转换为字符 数组后，按升序字典序对其进行排序。

步骤 3：使用排列 函数，从第一个排列开始，计数到第 N 个排列。

步骤 4：从末尾遍历数组，找到第一个位置 a，使得 s[a] < s[a + 1]。

步骤 5：从数组末尾 (s[b]) 找到比 s[a] 小但比 s[a] 大的字符，然后交换它们。

步骤 6：翻转 a 位置之后的子数组，以获得下一个最小的字典序。

步骤 7：将字符数组转换为字符串后，打印第 N 个字典序排列。

实施

文件名：LexicographicPermutations.java

输出

 
The lexicographic permutation is given by HWdellrloo   

复杂度分析

上述代码的时间复杂度为 O(n + |S| log |S|)，其中 S 是按对数线性时间排序的。为了准确表示运行时间的增长，即使 `next_permutation` 的均摊时间复杂度是常数且 n 与 |S| 无关，也必须将其包含在最终的时间复杂度表示中。空间复杂度为 O(1)。