53. Next Permutation

Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Solution:

From back to front, find the first index i that nums[i] < nums[i + 1].

From back to i, find the first index j that nums[j] > nums[i].

Swap nums[i] and nums[j].

Reverse nums[i + 1, end].

The time complexity is O(n) and the space complexity is O(1).

public class Solution {

    /**

     * @param nums: A list of integers

     * @return: A list of integers

     */

    public int[] nextPermutation(int[] nums) {

        // write your code here

        // int reverseIndex= -1;

        // for(int i = nums.length - 2; i >= 0; i--) {

        //     if(nums[i] <= nums[i+1]) {

        //         swap(nums, nums[i], nums[i+1]);

        //         reverseIndex = i+1;

        //         break;

        //     }

        // }

        

        

        int i = nums.length - 2;

        

        // 找到第一个降序的

        while (i >= 0 && nums[i+1] <= nums[i]) {

            i--;

        }

        

        

        if (i >= 0) {

            int j = nums.length - 1;

            while (j >= i && nums[j] <= nums[i]) {

                j--;

            }

            swap(nums, i, j);

        }

        reverse(nums, i + 1, nums.length-1);

        

        return nums;

    }

    

    void swap(int[] nums, int j, int k) {

        int temp = nums[j];

        nums[j] = nums[k];

        nums[k] = temp;

    }

    

    void reverse(int[] nums, int start, int end) {

        while(start < end) {

            swap(nums, start, end);

            start++;

            end--;

        }

    }

}