https://www.codewars.com/kata/58ad3****c5/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://51itzy.com/kjqy/2143.html