题目主要信息

1、给出一个数组的排列

2、找到该数组的下一个排列，使得新数组是大于该数组的最小数组

方法一:两次扫描

具体方法

注意到下一个排列总是比当前排列要大，除非该排列已经是最大的排列。我们希望找到一种方法，能够找到一个大于当前序列的新序列，且变大的幅度尽可能小。具体地：

1. 我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。
2. 同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。

以547532为例，我们需要将其排序成552347

首先找到第一对升序数对，这里我们找到的是(4,7)

然后寻找4后面比4大的最小值，这里比4大的数有7和5，取最小值5

交换4和5

最后升序排序5之后的元素，得到答案552347

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] nextPermutation (int[] nums) {
        // write code here
        int len = nums.length;
        int i = len-2;
        int j = len-1;
        int k = len-1;
        while(i>=0 && nums[i]>=nums[j]){
            i--;
            j--;
        }//从后往前找
        if(i>=0){//不是最后一个序列
            while(nums[i]>=nums[k]){
                k--;
            }
            swap(nums,i,k);
        }
        reverse(nums,j,len-1);
        return nums;
    }
    public void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;

    }
    public void reverse(int[] nums,int a,int b){
        while(a<b){
            swap(nums,a++,b--);
        }
    }
}

复杂度分析

• 时间复杂度：$O(N)O(N)$，找到第一个非递减数$O(N)O(N)$，找到最后一个比他大的数$O(N)O(N)$，反转$O(N)O(N)$
• 空间复杂度：$O(1)O(1)$，只需要常数空间储存若干变量

方法二：两次扫描+寻找优化

具体方法

第一个方法中，主要包括三步

1. 找到第一个非递减数
2. 找到最后一个比他大的数
3. 反转

第二步中，由于后续数为递减数组，因此可以用二分查询来进行优化

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] nextPermutation (int[] nums) {
        // write code here
        int len = nums.length;
        int i = len-2;
        int j = len-1;
        int k = len-1;
        while(i>=0 && nums[i]>=nums[j]){
            i--;
            j--;
        }//从后往前找第一个非递减数
        if(i>=0){//不是最后一个序列
            int l = i;
            int r = len;
            while(l<r){  //二分方法
                int mid = (r+l)/2;
                if(nums[mid]<=nums[i]){
                    r = mid;
                }else{
                    l = mid+1;
                }
            }
            swap(nums,i,l-1);
        }
        reverse(nums,j,len-1);
        return nums;
    }
    public void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;

    }
    public void reverse(int[] nums,int a,int b){
        while(a<b){
            swap(nums,a++,b--);
        }
    }
}

复杂度分析

• 时间复杂度：$O(N)O(N)$，找到第一个非递减数$O(N)O(N)$，找到最后一个比他大的数$O(logN)O(logN)$，反转$O(N)O(N)$
• 空间复杂度：$O(1)O(1)$，只需要常数空间储存若干变量