漫画：什么是字典序算法？

青旅半醒 2023-07-12 11:53 14阅读 0赞

![format_png][]

![format_png 1][]

**—————  第二天  —————**

![format_png 2][]

![format_png 3][]

![format_png 4][]

**算法题目：**

给定一个正整数，实现一个方法来求出离该整数最近的大于自身的“换位数”。

什么是换位数呢？就是把一个整数各个数位的数字进行全排列，从而得到新的整数。例如53241和23541。

小灰也不知道这种经过换位的整数应该如何称呼，所以姑且称其为“换位数”。

题目要求写一个方法来寻找最近的且大于自身的换位数。比如下面这样：

输入**12345**，返回**12354**

输入**12354**，返回**12435**

输入**12435**，返回**12453**

![format_png 5][]

![format_png 6][]

**小灰发现的“规律”：**

输入**12345**，返回**12354**

12354 - 12345 = **9**

刚好相差9的一次方

输入**12354**，返回**12435**

12435 - 12354 = **81**

刚好相差9的二次方

所以，每次计算最近的换位数，只需要加上9的N次方即可？

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

————————————

![format_png 11][]

![format_png 12][]

![format_png 13][]

![format_png 14][]

![format_png 15][]

![format_png 16][]

举一个栗子：

给定1,2,3,4,5这几个数字。

最大的组合：**54321**

最小的组合：**12345**

![format_png 17][]

比如给定整数12354，如何找到离它最近且大于它的换位数呢？

为了和原数接近，我们需要**尽量保持高位不变，低位在最小的范围内变换顺序**。

那么，究竟需要变换多少位呢？这取决于当前整数的**逆序区域**。

![format_png 18][]

如果所示，12354的逆序区域是最后两位，仅看这两位已经是当前的最大组合。若想最接近原数，又比原数更大，必须从**倒数第3位**开始改变。

怎样改变呢？12345的倒数第3位是3，我们需要从后面的逆序区域中寻找到刚刚大于3的数字，和3的位置进行互换：

![format_png 19][]

互换后的临时结果是12453，倒数第3位已经确定，这时候最后两位仍然是逆序状态。我们需要把最后两位**转变回顺序**，以此保证在倒数第3位数值为4的情况下，后两位尽可能小：

![format_png 20][]

这样一来，我们就得到了想要的结果**12435**。

![format_png 21][]

![format_png 22][]

**获得最近换位数的三个步骤：**

1.从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界

2.把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置

3.把原来的逆序区域转为顺序

![format_png 23][]

1.  `//主流程，返回最近一个大于自身的相同数字组成的整数。`
2.  `public static int[] findNearestNumber(int[] numbers){`
3.  `   //拷贝入参，避免直接修改入参`
4.  `   int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);`
5.  `   //1.从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界`
6.  `   int index = findTransferPoint(numbersCopy);`
7.  `   //如果数字置换边界是0，说明整个数组已经逆序，无法得到更大的相同数字组成的整数，返回自身`
8.  `   if(index == 0){`
9.  `       return null;`
10. `   }`
11. `   //2.把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置`
12. `   exchangeHead(numbersCopy, index);`
13. `   //3.把原来的逆序区域转为顺序`
14. `   reverse(numbersCopy, index);`
15. `   return numbersCopy;`
16. `}`
17.  
18. `private static int findTransferPoint(int[] numbers){`
19. `   for(int i=numbers.length-1; i>0; i--){`
20. `       if(numbers[i] > numbers[i-1]){`
21. `           return i;`
22. `       }`
23. `   }`
24. `   return 0;`
25. `}`
26.  
27. `private  static int[] exchangeHead(int[] numbers, int index){`
28. `   int head = numbers[index-1];`
29. `   for(int i=numbers.length-1; i>0; i--){`
30. `       if(head < numbers[i]){`
31. `           numbers[index-1] =  numbers[i];`
32. `           numbers[i] = head;`
33. `           break;`
34. `       }`
35. `   }`
36. `   return numbers;`
37. `}`
38.  
39. `private static int[] reverse(int[] num, int index){`
40. `   for(int i=index,j=num.length-1; i<j; i++,j--){`
41. `       int temp = num[i];`
42. `       num[i] = num[j];`
43. `       num[j] = temp;`
44. `   }`
45. `   return num;`
46. `}`
47.  
48. `public static void main(String[] args) {`
49. `   int[] numbers = {1,2,3,4,5};`
50. `   for(int i=0; i<10;i++){`
51. `       numbers = findNearestNumber(numbers);`
52. `       outputNumbers(numbers);`
53. `   }`
54. `}`
55.  
56. `//输出数组`
57. `private static void outputNumbers(int[] numbers){`
58. `   for(int i : numbers){`
59. `       System.out.print(i);`
60. `   }`
61. `   System.out.println();`
62. `}`

这种解法拥有一个高大上的名字：**字典序算法**。

![format_png 24][]

![format_png 25][]

![format_png 26][]

**几点补充：**

**本漫画纯属娱乐，还请大家尽量珍惜当下的工作，切勿模仿小灰的行为哦。**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JpYkpwemtmaWNBeWhDVlR2eXlhVENJRldLQU9XYXk2MWNpYWN5Z3ppY0ZpY05GdkthUnhyNjdrbXd5aWJsd2x1YkQ1N3I1M1IxUWt4UjZZalEvNjQw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JpYkpwemtmaWNBeWhDVlR2eXlhVENJRlNuMDRCYk5sblVGTTVpYm9nS3FkYTNjMldCOXZLSEUzQ3h3eDBTYWRVck44WHlXNzNKTFUwSHcvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYndoRWtNTWJHOVZlYWE1dHRsTFpONklGcUhobjdCZ1A0eloxNUc2Z2pTNXZNemVJNDFBVzVqQS82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYmFLMDE3aWJQdkprUnAzbTc4WUp3V29mSTRxb0NocGdBSVk3c2RwQ2N4NzhndVZ3aHhyUVZrSWcvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BhWEQyb1VNODkyZHhtR04yOE9ZSE9Tdm9Eazc2d2lhSkRTVEZpYTloMkNWVGZqVlZhenFpY1NycXJlZkc5UGliOXNLOVVDZEtFUVJxUXZ3LzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BhWEQyb1VNODkyZHhtR04yOE9ZSE9QdEZNYnhtdmNPdWQ1R0R3TzFDSmlhVjc4U1E2QnEzRng2aWJ4SDR1Tmlja3BtSVRpYzhJS2FJclRRLzY0MA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BhWEQyb1VNODkyZHhtR04yOE9ZSE9kMnFNcGljeTVZVEU2SERLSkZ2QVlJdVpQdVN4VmZTYVZ2RHFoQ2xUaWI4OVdSdVBFSklTQkgxUS82NDA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BhWEQyb1VNODkyZHhtR04yOE9ZSE90NUNoZmhjZHhraGJuTDNjdTZtaWFzMlFpYmN1OGlhaHV6TUppYVdlTWdDd3NRYWg0cHBpY285dnEwUS82NDA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BhWEQyb1VNODkyZHhtR04yOE9ZSE90ZHdBa0JFcWM0MEtSV1JJRkpXc2JTdDc5d3lBWk1JbmlidGFiYTZ4ZVpsOE1FTDB4VUFzWXZRLzY0MA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BhWEQyb1VNODkyZHhtR04yOE9ZSE9tWVVpY3NpYzNibXA5YkdMOE1hdWZ3cEtiYnkyb0xySHJNd0xzb1U0Q1RxQXdyRDNFYUVHQU82QS82NDA?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BhWEQyb1VNODkyZHhtR04yOE9ZSE93WURmekNFa2VmcUhFMFhyU0R2MjVPdGVFUmFia1hyYzdWWFIzaWFLN1BqUnFtUGh1N0hOdEZ3LzY0MA?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3FGb3hNTUtNRjk5dUQ4VWdUOXdmcExEWllpYkI2ZWtONXhMWU8zdWliTmozY3J4Z05YNmo2Mk5WRE1KalFjaWN2WlJLTVo0dVNJNlkwemcvNjQw?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3FGb3hNTUtNRjk5dUQ4VWdUOXdmcEx5aDhwMHhDeWNjWkR1ancxdllscEh1VEpmbkVlcnZsb0xWNmp6a25JRWhpYVdMVU5GZzFiaE1RLzY0MA?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VhaWJOdWljZFZwdU0yeVh5cGliU2I0bDYzQnd0ZkRTbTlFUFpiTDZDUFI0bENZYUFmU2ZBSEhpYnl3LzY0MA?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VSYnBLOVg1ekw5RmZIM0JaaWFUckpWQUNhTElNMUw3bUZGNDZJU2hab09FT3U0alUyZFBTWEFRLzY0MA?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VnVkFMbVBCaWFTenJqcWVjd0ZhS25kOW5NSWxVYXlDSVpIWmdjU2ljdXF4Z2hPVEdLRFIzU1VRUS82NDA?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VpYjJ6ZkFNTmlhM01aZm5EMmFOaWM1blBtb1ZYSEFpYzVkSVQ2ZzRSWmJwa1NxYkFXeE5NYWljRXBSQS82NDA?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1U1VWliZXowT1EzOEY4Z1lWSUI3TktjaWJxYXNERlRvMDV5aWNwRE55b0hEMm9WbnZTN1ZBc2ZtQmcvNjQw?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VRSGxoVGliQkplWUNnZ1BudlY5aWE1VkIzRGpua3B4U1p2ZXkzZWRDOWpBaWF1SVJsVGlhaGhyWkRRLzY0MA?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VhcERrVVJBeFJZRDRUd0Z0R1RzbnJDdXA1UWliY25rMHRCQlZIamliWDNLaWFvMEUxUnN3Mm1zeEEvNjQw?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1V4MmpxTUlpYmdrZzBDaWFsVzN3bkYzTVhYWWZHcmljU2lhbW9pYnFVYmxZMzJpYXEwcFJkdWliekc1aWN3QS82NDA?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1V6YTZtSFZ2dzhMVVNNMGhYMnhjZjBDRzhpYk4yMWxpYkwwTEJpYWdUaWF1M1FMaHVpYzFpYURmZnNKTkEvNjQw?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VFbEo4QkZPMHBTN0RwTHZIZHBvMkhraG1relJwaWF1OXN2UTB0aWFJYlVzT2swd0hGeXVnZFNpYXcvNjQw?x-oss-process=image/format,png
[format_png 23]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VBaWI2aWF1cmhpYVJpY2NvYWlhc01pYW92amliZ2o4cG5nMHFQdkhjNDNmNWg3eDdmSUJQSGdGOGlhbXMxQS82NDA?x-oss-process=image/format,png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VwbGt3a1g3S3RoNjc3Z2x1QU5PZXNMWGRiYXVzVDBvMUNtT1hldll0SzhLZWZpY3dJbW1hT0FnLzY0MA?x-oss-process=image/format,png
[format_png 25]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VVNTVzSnZVaWFMZFg2RUlnbkJaMnZvMG1zNlQyMU81RUt3c3BNdFZqSjN0VUVudVNhYjVjQXVBLzY0MA?x-oss-process=image/format,png
[format_png 26]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BjYnZxRWNhN3FLMDlkZWEyZXpra1VSaWN6NVJOcVZoaDJJYlpnU1Vkb1h1VmpGRVBiaWJNTzg2c21FbUlweUFPN2tUeUE5YlFoT3JUUS82NDA?x-oss-process=image/format,png