数据结构和算法（刷题）- 寻找全排列后的下一个数

寻找全排列后的下一个数

1. 问题：给出一个正整数，找出这个正整数所有数字全排列的下一个数。也就是这个数的数字全排列，找到一个比原数大的而且只比原数大的数。

2. 例子：输入：12345 输出：12354

3. 解法：

   • 步骤：

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

   • 代码：

     public class FindNearestNumber {
     
         public static int[] findNearestNumber(int[] numbers){
             //1.从后向前查看逆序区域，找到逆序区域的第一位，也就是数字置换的边界
             int index = findTransferPoint(numbers);
             //如果数字置换边界是0，说明整个数组已经逆序，无法得到更大的相同数字组成的整数，返回null
             if(index == 0){
                 return null;
             }
             //2.把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置
             //拷贝入参，避免直接修改入参
             int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);
             exchangeHead(numbersCopy, index);
             //3.把原来的逆序区域转为顺序
             reverse(numbersCopy, index);
             return numbersCopy;
         }
     
         private static int findTransferPoint(int[] numbers){
             // 从后往前查看，当前数字比前一个数大了，逆序区域结束，返回当前索引
             for(int i=numbers.length-1; i>0; i--){
                 if(numbers[i] > numbers[i-1]){
                     return i;
                 }
             }
             return 0;
         }
     
         private static int[] exchangeHead(int[] numbers, int index){
             // 得到逆序区域的前一位，它要和逆序区域中大于它的最小元素交换
             int head = numbers[index-1];
             // 从后往前，遍历逆序区域，遍历到的第一个大于它的就是最小大于它的，就结束循环
             for(int i=numbers.length-1; i>0; i--){
                 if(head < numbers[i]){
                     numbers[index-1] =  numbers[i];
                     numbers[i] = head;
                     break;
                 }
             }
             return numbers;
         }
     
         // 把index后面的元素交换顺序
         private static int[] reverse(int[] num, int index){
             for(int i=index,j=num.length-1; i<j; i++,j--){
                 int temp = num[i];
                 num[i] = num[j];
                 num[j] = temp;
             }
             return num;
         }
     
         public static void main(String[] args) {
             int[] numbers = {1,2,3,4,5};
             //打印12345之后的10个全排列整数。numbers一直在变化，找到更大的
             for(int i=0; i<10;i++){
                 numbers = findNearestNumber(numbers);
                 outputNumbers(numbers);
             }
         }
     
         //输出数组
         private static void outputNumbers(int[] numbers){
             for(int i : numbers){
                 System.out.print(i);
             }
             System.out.println();
         }
     }
     
     

   • 思考：三个步骤，每一步都是$O(n)$，因此时间复杂度是$O(n)$