寻找全排列的下一个数
    给出一个正整数，找出这个正整数所有数字全排列的下一个数。
    说通俗点就是在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。让我们举几个例子。
    如果输入12345，则返回12354。
    如果输入12354，则返回12435。
    如果输入12435，则返回12453。

    获得全排列下一个数的3个步骤。

    1. 从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。
    2. 让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。
    3. 把原来的逆序区域转为顺序状态。

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

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

    时间复杂度字典序算法 - 图1