找规律

题目链接-来源：力扣（LeetCode）

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

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

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

示例 1：

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

思路：

考虑「下一个排列」的特征。

  • 首先，可以想到，如果数组为完全逆序，则意味着我们找不到下一个排序了。此时我们就必须重排数组。
  • 反之，如果数组存在顺序对（即存在 nums[i] < nums[i + 1]），我们可以判定数组中一定存在「下一个排列」。

对于字典序，靠前的元素的权重大于靠后的元素，于是我们应该优先考察靠后元素。我们可以从后往前遍历数组，跳过逆序对，当我们遍历到第一组顺序对（记为 nums[i]，nums[i + 1]）时，我们有如下推论：

  • nums[i + 1] 以及之后的元素必为逆序排列， 且 nums[i + 1] 从下标 i 到 length - 1 这个局部的最大值。（因为我们是从后向前遍历的，否则就不会停在这里）。
  • 对于下标 i + 1 到 length - 1 的这个局部，由于是逆序排列，所以已经是当前局部字典序的最大值，同时也是对于下标 i 到 length - 1 这个局部以 nums[i] 为首的序列的字典序最大值。

那么下一个排列就应当具有如下特征：

  • 记下标 i 到 length - 1 这个局部当中，满足大于 nums[i] 的元素的最小值为 nums[j]。下一个排列的头部元素一定是 nums[j]，并且由于 nums[i + 1] 之后的元素都是逆序，我们只要从后往前找到第一个大于 nums[i] 的元素，即为 nums[j] 。
  • 确定头部元素以后，我们只要保证之后的元素是局部「最小排列」即可（即局部升序排列）。我们在前一步寻找 nums[j] 时，可以顺便交换 nums[j] 与 nums[i] 的位置，这样 nums[j] 就换到了头部，而 nums[i] 放到后部当中恰好使得该局部依然保持逆序。对于逆序序列，我们只要从头尾开始分别两两交换前后元素，即可获得一个升序序列。
    这样处理后的元素即为我们所需的排列。细节，对于完全逆序序列，我们只要增加一个额外判断 i 是否等于 0 即可。

时间复杂度：O(n)
空间复杂度：O(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
class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        boolean Swapped = false;
        for (int i = len - 1; i >= 0; i--) {
            if (i == 0 || nums[i] > nums[i - 1]) {
                for (int j = len - 1; j >= i; j--) {
                    if (i == 0 || nums[j] > nums[i - 1]) {
                        if (i != 0) {
                            swap(nums, i - 1, j);
                        }
                        for (int l = i, r = len - 1; l < r; l++, r--) {
                            swap(nums, l, r);
                        }
                        break;
                    }
                }
                break;
            }
        }
        
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
}