Next Permutation

发表于   |   分类于 ，

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

描述

给出当前序列的下一个序列（要求得到的序列，仅仅只比当前序列大），若当前序列为降序，则输出升序

分析

  • 当序列是降序时（最大序列），不存在比这个序列大的序列
  • 当序列是升序时（最小序列），不存在比这个序列小的序列

如图所示，假设序列长度为 len ，a[i] ~ a[len-1] 是降序序列，即最大的序列。当 a[i-1] < a[i] 时，先从序列 a[i-1] ~ a[len-1] 中选取一个数（仅仅只大于 a[i-1]），与 a[i-1] 交换，那么此时序列已经比原序列要大，之后只需要将 a[i] ~ a[len-1] 序列变成升序序列，即使 a[i] ~ a[len-1] 为最小序列

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    public void nextPermutation(int[] nums) {

        int i = nums.length - 2;

        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }

        reverse(nums, i + 1);
    }

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

        int i = start, j = nums.length - 1;

        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    public void swap(int nums[], int i, int j) {

        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}