Question:

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 and use only constant 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

Thinking:

  • Method1:
    1. 从后向前遍历，找到第一个不满足降序的元素；若初始序列全部是降序，则i为-1，直接跳转至3
    2. 将该元素同它后面的元素中比它大的第一个元素交换；
    3. 将之后的元素按照升序排序。
class Solution {
    public void nextPermutation(int[] nums) {
        if(null == nums || nums.length == 0) return;
        int len = nums.length;
        int index = -1;
        for(int i = len - 1; i >= 1; i--){
            int j = i - 1;
            if(nums[i] > nums[j]){
              index = j;
                break;
            }
        }
        if(index == -1){
            Arrays.sort(nums);
            return;
        }
        int temp = nums[index];
        int min = Integer.MAX_VALUE;
        int pos = -1;
        for(int k = index + 1; k < len; k++){
            if(nums[k] > temp && nums[k] < min){
                pos = k;
                min = nums[k];
            }
        }
        swap(nums, index, pos);
        Arrays.sort(nums, index + 1, len);
    }
    public static void swap(int[] nums, int p, int k){
        int temp = nums[p];
        nums[p] = nums[k];
        nums[k] = temp;
    }
}

二刷

没有参考一刷，直接写出来了，但是要注意一个问题，就是判断非递增的时候需要考虑相等的情况。

class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length == 0) return;
        int len = nums.length;
        int i = len - 2;
        for(; i >= 0; i--){
            if(nums[i] >= nums[i + 1]) continue;
            int min = Integer.MAX_VALUE, count = 0;
            for(int j = i + 1; j < len; j++){
                if(nums[j] > nums[i] && nums[j] < min){
                    count = j;
                    min = nums[j];
                }
            }
            swap(nums, count, i);
            break;
        }
        Arrays.sort(nums, i + 1, len);
    }
    private void swap(int nums[], int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}