31. Next Permutation - jiejackyzhang/leetcode-note GitHub Wiki

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.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

这道题的关键是找到next permutation的特征。 注意到若数组中数字是呈倒序排列，则它是greatest permutation（如3,2,1）。

因此关键是找出从右边开始第一个不是倒序的数nums[i]，则将它替换为它右边比它大的数中最小的那个，然后将它右边的数顺序排列，即为next permutation。 注意到swap之后，nums[i]右边的数仍是倒序排列，因此只需将这些数reverse一下即可。

一个特例是nums已经是greatest permutation，即它本身就是倒序排列，则我们应将它reverse，使它变为smallest permutation。

public class Solution {
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int start) {
        int i = start;
        int j = nums.length-1;
        while(i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while(i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        } 
        // if found the rightmost element not in descending order
        // swap nums[i] with the number just larger than it
        if(i >= 0) {
            int j = nums.length - 1;
            while(j > i && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        // make smallest permutation at the right of nums[i]
        // reverse nums starting from i+1
        // if nums is the largest permutation, i = -1, then reverse nums 
        reverse(nums, i+1);
    }
}
⚠️ **GitHub.com Fallback** ⚠️