https://www.codewars.com/kata/58ad317d1541651a740000c5/java
一个串的全排列 例如abc 为 "abc", "acb", "bac", "bca", "cab", "cba"
求全排列的算法为 循环该串，轮流取出一个字符，之后再求剩下的串的全排列在进行合并。
字典序意思是两个串比较，字符顺序小的在前，比如按照字典序"acb"<"bac"
该题要求一个串的字典序全排列的中间值，第一反应是不能按照暴力法求出全排列再取中值，因为全排列是n!增长的。
那么接下来找规律，可以看到每个字符开头的全排列个数是相同的，假设输入为abcd，他的字典序全排列为
[abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda, bdac, bdca, cabd, cadb, cbad, java基础字典表设计 cbda, cdab, cdba, dabc, dacb, dbac, dbca, dcab, dcba]
可以看出，如果输入字符串为偶数的话，那么中间值就是b开头的最后一个排列即bdca，也就是以b开头的串字典序最大的值，因为字典序是最大的，所以b后面的字幕为逆字典序。
偶数的中间值位置示意如下
如果是奇数的话,那么中值示意如下。
可以看出是中间那块的中值，那么这个怎么求呢，因为奇数减去一个值就是偶数，所以还是先算出开头字母，将其减掉得出一个新的字符串，转化为偶数情况。
按照此规律编写代码如下
此算法最多只要计算两次，所以为O(1)时间复杂度，不过该题的输入不是按顺序的，所以需要先进行排序，那么时间复杂度就是O(nlogn)了。
在浏览其他人答案的时候似乎还有一些别的规律，看到一个只用算一次的算法如下
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/26023.html