Using the math, four steps, JAVA code


  • 0
    F
    There are four steps in this algorithm:
    1. find the largest k such that a[k]<a[k+1]
    2. find the largest i such that a[k]<a[i]
    3. swap(a[k],a[i])
    4. reverse(a,k+1,n-1)
    and here is my JAVA code:
    
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int k = n - 1;
        while (k >= 1 && nums[k] <= nums[k - 1])
            k--;
        if (k == 0) {
            reverse(nums, 0, n - 1);
            return;
        }
        k--;
        int i = n - 1;
        while (nums[k] >= nums[i])
            i--;
        swap(nums, k, i);
        reverse(nums, k + 1, n - 1);
    }
    
    public void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }
    
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.