题解 | #下一个排列#

下一个排列

http://www.nowcoder.com/practice/50b0b87e50be4944b34cb0f2ce618197

题目：

给定一个数组，将数组重新排列，得到一系列数组排列S，请你从S中，找出恰好比当前数组排列字典序大于1的数组排列。该题数组排列的字典序大小排序规则：2个数组排列的元素按顺序比较，直到数组元素不相等为止，不相等的第一个元素，谁的元素大，谁的字典序比较大，比如数组a=[1,2,3]与数组b=[1,3,2]比较：a[0]=b[0]，a[1]<b[1]，此时出现了第一个不相同的，且a[1]<b[1]，则a的字典序小于b的字典序。且[1,3,2]的字典序在排列S中，正好在[1,2,3]的后面，视为[1,3,2]的字典序比[1,2,3]的字典序大于1。 3.如果不存在更大的数组排列，则返回最小的数组排列。

方法一：两次扫描+排序

要找到下一个排列，首先需要在左边找到一个较小数，并且该数越靠右越好，在右边找到一个较大数，较大数即为从后往前第一个比较小数大的数，交换这两个数。

具体思想为：

从右往左找到第一对升序的数，记录位置为l
从右边到左边找到第一个比nums[l]大的数，交换这两个数
对nums[l+1,end]进行排序

alt

java
javascript

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    
    public int[] nextPermutation (int[] nums) {
        // write code here
        int l=0,r=nums.length-1;
        for(int i=0;i<nums.length-1;i++){//从左往右找到降序排列，并且越靠右越好
            if(nums[i+1]>nums[i]){
                l=i;
            }
        }
        for(int i=nums.length-1;i>l;i--){//从右往左找到第一个比nums[l]大的数
            if(nums[i]>nums[l]){
                r=i;
                break;
            }
        }
        int temp=nums[l];//交换两个数
        nums[l]=nums[r];
        nums[r]=temp;
        Arrays.sort(nums,l+1,nums.length);//从左指针后面处升序排列
        return nums;
        
    }
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型一维数组
 */
function nextPermutation( nums ) {
    // write code here
    let l=0,r=nums.length-1;
    for(let i=0;i<nums.length-1;i++){
        if(nums[i+1]>nums[i]){
            l=i;
        }
    }
    for(let i=nums.lenth-1;i>l;i--){
        if(nums[i]>nums[l]){
            r=i;
            break;
        }
    }
    let temp=nums[l];
    nums[l]=nums[r];
    nums[r]=temp;
    let sortArr=nums.splice(l+1).sort((a,b)=>a-b);
    return nums.slice(0,l+1).concat(...sortArr);
}
module.exports = {
    nextPermutation : nextPermutation
};

复杂度：

时间复杂度： $O(nlog_{2}n)$ ,排序算法的时间复杂度为 $O(nlog_{2}n)$
空间复杂度： $O (1)$ ，常数级空间复杂度

方法二：两次扫描+反转数组

在方法一中的第一步中，在从右往左找第一对升序数时，我们可以证明nums[l+1,end]是降序的，因此，在交换完两个数后直接对nums[l+1,end]反转即可

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    
    public int[] nextPermutation (int[] nums) {
        // write code here
        int l=0,r=nums.length-1;
        for(int i=0;i<nums.length-1;i++){//从左往右找到降序排列，并且越靠右越好
            if(nums[i+1]>nums[i]){
                l=i;
            }
        }
        if(l==0)return reverse(nums,0);
        for(int i=nums.length-1;i>l;i--){//从右往左找到第一个比nums[l]大的数
            if(nums[i]>nums[l]){
                r=i;
                break;
            }
        }
        System.out.print(l+" "+r);
        swap(nums,l,r);//交换两个数
        return reverse(nums,l+1);
        
    }
  //交换两个数
    void swap(int[]nums,int a,int b){
        int temp=nums[a];
        nums[a]=nums[b];
        nums[b]=temp;
    }
  //反转数组
    int[]reverse(int[]nums,int start){
        for(int i=start,j=nums.length-1;i<j;i++,j--){
            swap(nums,i,j);
        }
        return nums;
    }
    
}