Next Permutation

Source

LintCode 52 Next Permutation

Problem

Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Example

For [1,3,2,3], the next permutation is [1,3,3,2]

For [4,3,2,1], the next permutation is [1,2,3,4]

Solution

public int[] nextPermutation(int[] nums) {
    // Step 1: search for swap place, where nums[k] < nums[k+1]
    int k = -1;
    for (int i = nums.length - 2; i >= 0; i--) {
        if (nums[i] < nums[i+1]) {
            k = i;
            break;
        }
    }

    // If k is still -1, meaning it's already the largest permutation, just reverse the array
    if (k == -1) {
        reverse(nums, 0, nums.length - 1);
        return nums;
    }

    // find the first place that num[i] > num[k] from the right
    // as in this case [1,4,5,5,2], the next step should be [1,5,5,4,2] not [1,5,4,5,2]
    int i = nums.length -1;
    while (i > k && nums[i] <= nums[k]) i--;

    // swap two number
    int tmp = nums[i];
    nums[i] = nums[k];
    nums[k] = tmp;

    // reverse all the numbers from k+1 to last index in order to get ascending order (i.e. smallest number)
    reverse(nums, k+1, nums.length - 1);

    return nums;
}

private void reverse(int[] nums, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}