5.8.1 一道关于数字的题目
下面我来考查你一道算法题，假设给出一个正整数，请找出这个正整数所有数字全排列的下一个数。
题目
给出一个正整数，找出这个正整数所有数字全排列的下一个数。
说通俗点就是在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。让我们举几个例子。
如果输入12345，则返回12354。
如果输入12354，则返回12435。
如果输入12435，则返回12453。
让我想一想啊……
我发现了，这里面有个规律！让我来解释一下。
小灰发现的“规律”如下。
输入12345，返回12354，那么
12354 - 12345 = 9，
刚好相差9的一次方。
输入12354，返回12435，那么
12435 - 12354 = 81，
刚好相差9的二次方。
所以，每次计算最近的换位数，只需要加上9的n次方即可。
怎么样，我是不是很机智？
这算哪门子规律？ 12453-12435= 18，24135-23541=594，也并不都是9的整数次幂啊！
啊，尴尬了……
呵呵，今天就到这里，回家等通知去吧！
5.8.2 解题思路
小灰，你刚刚去面试了？结果怎么样？
唉……
大黄，你能不能给我讲讲，怎么样寻找一个整数所有数字全排列的下一个数？
好啊，在给出具体解法之前，小灰你先思考一个问题：由固定几个数字组成的整数，怎样排列最大？怎样排列最小？
让我想一想啊……
知道了，如果是固定的几个数字，应该是在逆序排列 的情况下最大，在顺序排列 的情况下最小。
举一个例子。
给出1、2、3、4、5这几个数字。
最大的组合：54321 。
最小的组合：12345 。
没错，数字的顺序和逆序，是全排列中的两种极端情况。那么普遍情况下，一个数和它最近的全排列数存在什么关联呢？
例如给出整数12354，它包含的数字是1、2、3、4、5，如何找到这些数字全排列之后仅大于原数的新整数呢？
为了和原数接近，我们需要尽量保持高位不变，低位在最小的范围内变换顺序 。
至于变换顺序的范围大小，则取决于当前整数的逆序区域 。
如图所示，12354的逆序区域是最后两位，仅看这两位已经是当前的最大组合。若想最接近原数，又比原数更大，必须从倒数第3位 开始改变。
怎样改变呢？12345的倒数第3位是3，我们需要从后面的逆序区域中找到大于3的最小的数字，让其和3的位置进行互换。
互换后的临时结果是12453，倒数第3位已经确定，这个时候最后两位仍然是逆序状态。我们需要把最后两位转变为顺序状态 ，以此保证在倒数第3位数值为4的情况下，后两位尽可能小。
这样一来，就得到了想要的结果12435 。
有些明白了，不过还真是复杂呀！
看起来复杂，其实只要3个步骤。
获得全排列下一个数的3个步骤。
1. 从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。
2. 让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。
3. 把原来的逆序区域转为顺序状态 。
最后让我们用代码来实现一下。这里为了方便数字位置的交换，入参和返回值的类型都采用了整型数组。
1. public static int[] findNearestNumber(int[] numbers){
2. //1. 从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界
3. int index = findTransferPoint(numbers);
4. // 如果数字置换边界是0，说明整个数组已经逆序，无法得到更大的相同数
5. // 字组成的整数，返回null
6. if(index == 0){
7. return null;
8. }
9. //2.把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置
10. //复制并入参，避免直接修改入参
11. int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);
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]){
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
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. //打印12345 之后的10个全排列整数
51. for(int i=0; i<10;i++){
52. numbers = findNearestNumber(numbers);
53. outputNumbers(numbers);
54. }
55. }
56.
57. // 输出数组
58. private static void outputNumbers(int[] numbers){
59. for(int i : numbers){
60. System.out.print(i);
61. }
62. System.out.println();
63. }
这种解法拥有一个“高大上”的名字：字典序算法 。
小灰，你说说这个解法的时间复杂度是多少？
该算法3个步骤每一步的时间复杂度都是O(n)，所以整体时间复杂度也是O(n) ！
完全正确。关于这道算法题的解答就介绍到这里，咱们下一节再会！