31. 下一个排列

题目

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：

输入：nums = [1]
输出：[1]

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

思路

以排列 [4,5,2,6,3,1] 为例：

假如我们要找到它的最小排列的最小思路是什么：

  1. 大数在前面，后面的大数替换前面的一个小数
  2. 我们要替换的小数要尽可能的靠近末尾的位置
  3. 所以我们要把这个数变为453621，但是我们发现这个数也不是临近的的数，我们需要把3只有的数变为一个最小值，也就是453126

所以整体思路也就出来了，我们使用两次循环

第一次循环从后向前找，找到一个临近的数但是后面的数比前面的数大（2,6）

第二次循环从前（2的位置）向后，找到比第一次循环的下降的值（2）大的数

第三次反转2后面的数，使后面的数变为一个最小值

实现

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
39
40
41
42
43
private static class Solution {
    int[] nums;

    public void nextPermutation(int[] nums) {
        this.nums = nums;
        int leftIndex = -1, rightIndex = 0;
        // 第一次循环，从后向前找，找到两个临近的的从后向前递减的值
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                leftIndex = i - 1;
                break;
            }
        }
        if (leftIndex >=0) {
            // 第二次循环，第一次找到的值中从后前前找，找到一个比这个值大的数
            for (int i = nums.length - 1; i > 0; i--) {
                if (nums[i] > nums[leftIndex]) {
                    rightIndex = i;
                    break;
                }
            }
            // 交换leftINdex 和 rightIndex
            swap(leftIndex, rightIndex);
        }

        // 翻转第一次循环找到的值后面的数
        reserve(leftIndex + 1);

    }

    private void reserve(int leftIndex) {
        int right = nums.length - 1;
        while (leftIndex < right) {
            swap(leftIndex++, right--);
        }
    }

    private void swap(int leftIndex, int rightIndex) {
        int temp = nums[leftIndex];
        nums[leftIndex] = nums[rightIndex];
        nums[rightIndex] = temp;
    }
}