LeetCode(77) -- 31

P31. Next Permutation (Medium)

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

My Solution

排序时，任何子序列的起始状态都是升序的，结束状态都是降序的。所以想知道当前排序的下一个排序，就要先找到现在那些已经排好了，也就是从后往前数降序的那部分。比如4，1，3，5，2这个序列，5，2就是排好了的，也就是说以4，1，3开头的都数过了，一下个该数谁了呢？该把3换掉了，4，1保持不变。所以就要考虑用5换3，因为5比3大。替换完之后，后面的那部分还依然是降序的，但是以4，1，5开头的，后面应该先数升序的情况，所以要把后面的整体反转。

public class P31_NextPermutation {
    public void nextPermutation(int[] nums) {
        int length = nums.length;
        int i;
        for (i = length - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                int next = length - 1;
                while (nums[next] <= nums[i - 1]) {
                    next--;
                }
                int temp = nums[i - 1];
                nums[i - 1] = nums[next];
                nums[next] = temp;
                int l = i, r = length - 1;
                while (l < r) {
                    temp = nums[l];
                    nums[l] = nums[r];
                    nums[r] = temp;
                    l++;
                    r--;
                }
                break;
            }
        }
        if (i == 0) {
            Arrays.sort(nums);
        }
    }

    public static void main(String[] args) {
        int[] test = {4,1,3,5,2};
        new P31_NextPermutation().nextPermutation(test);
        System.out.println("test = " + Arrays.toString(test));

    }
}

80%

The Best Solution

class Solution {
    public void nextPermutation(int[] nums) {
        
        int len = nums.length;
        int j=len-2;
        while(j>=0 && nums[j+1]<=nums[j]){
            j--;
        }
        int i=len-1;
        if(j>=0){
            while(i>=0 && nums[i]<=nums[j]){
                i--;
            }
        swap(nums,i,j);
        }
        i=len-1;
        j=j+1;
        while(j<i){
            swap(nums,j,i);
            j++;
            i--;
        }
    }
    
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]= nums[j];
        nums[j]= temp;
    }
}