Next Permutation

ID: 31

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

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

Input: nums = [1,2,3,6,5,4]
Output: [1,2,4,3,5,6]

Idea

Swap + reverse + condition check

Check if given nums[] in desending order, if yes, just reverse

Locate ith element that breaks the desending order, check from the end for the first element greater than ith element

Swap these two element and reverse the i+1th element to end(1,2,3,6,5,4-->1,2,4,6,5,3[6 is not the least element greater than 4, but 3 is]-->1,2,4,3,5,6)

Code

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

    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }