[Leetcode]31. Next Permutation

Question

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, do not allocate extra memory.

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

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

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

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

Solution

This meaning of this problem is to find the next closest number that greater than current number. If the number is in descending order, it means it’s already the biggest permutation, then sort it in ascending order.

There are some principles we should to know before start to solve this problem:

1. Descending order is the biggest permutation of a set of numbers.
2. On the contrary, ascending is the smallest permutation.
3. To minimize the increased amount, we have to make the highest changed position increase as less as we can.

Following the principles we can solve this problem in 3 steps:

1. Start from tail, find the first element with index i that satisfy num[i-1] < num[i]. So from num[i] to num[n-1] is in descending order.
2. In order to minimize the increase amount, we need to find a closest number with num[i-1] in the descending list to exchange with num[i-1].
3. After exchange, from num[i] to num[n-1] is still in descending number, it means it’s in the greatest permutation. In order to keep the whole number increase minimum, remember we just increased the highest position? Then we need to make the remaining part of as small as possible, so we just reversely sort the num[ i , n-1 ].

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length <= 1){
            return;
        }
        
        int numberLength = nums.length;
        int firstIndex = -1;
        int secondIndex = -1;
        int exchangeNumberIndex = -1;
        for(int i = numberLength-1; i >0; i--){
            if( nums[i-1] < nums[i]){
                firstIndex = i-1;
                secondIndex= i;
                break;
            }
        }
        if( firstIndex == -1 ){
            reverse(0,numberLength-1,nums);
            return;
        }
        for(int i = numberLength-1 ; i >= secondIndex ; i--){
            if( nums[i] > nums[firstIndex] ){
                exchangeNumberIndex = i;
                break;
            }
        }
        swap(firstIndex, exchangeNumberIndex, nums);
        reverse(secondIndex,numberLength-1,nums);

    }
    
    private void swap(int n, int m, int[] numbers){
        int temp = numbers[n];
        numbers[n] = numbers[m];
        numbers[m] = temp;
    }
    
    private void reverse(int startIndex, int endIndex, int[] numbers){
        while( startIndex < endIndex ){
            swap(startIndex++,endIndex--,numbers);
        }
    }
}