31.下一个排列

linwt · linwt · commit ab87771caf3c · 2022-04-03T22:35:20.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -10,6 +10,7 @@
 20. 有效的括号
 21. 合并两个有序链表
 22. 括号生成
+31. 下一个排列
 37. 解数独
 39. 组合总和
 40. 组合总和 II
diff --git a/leetcode_Java/Solution0031.java b/leetcode_Java/Solution0031.java
@@ -0,0 +1,47 @@
+// 31. 下一个排列
+
+
+/*
+1、“下一个排列”定义：
+  1）给定数字序列的字典序中下一个更大的排列。可以理解成这些数字拼凑成的多个整数，升序排序，然后求当前整数的下一个整数
+  2）如果不存在下一个更大的排列，则将数字重新排列成最小的排列。即整数是最大的，那么整体升序排列得到一个最小的整数
+2、算法推导
+  1）我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数
+  2）我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，需要：
+    ① 在尽可能靠右的低位进行交换，需要从后向前查找
+    ② 将一个尽可能小的「大数」与前面的「小数」交换
+    ③ 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列
+3、算法过程
+  1）从后向前查找第一个相邻升序的元素对 (i-1,i)，满足 A[i-1] < A[i]，即找到第一个可交换的最低位「小数」。此时 [i,end) 必然是降序
+  2）在 [i,end) 从后向前查找第一个满足 A[i-1] < A[j] 的 j，即找到第一个可交换的值最小的「大数」。A[i-1]、A[j] 分别是「小数」、「大数」
+  3）将 A[i-1] 与 A[j] 交换
+  4）此时 [i,end) 必然是降序，逆置 [i,end)，使其升序
+  5）如果在步骤1找不到符合的相邻升序元素对，说明当前 [0,end) 为一个降序顺序，即最大的排序，则整体升序得到最小的排列
+
+1   2   3   8   5   7   6   4
+                ↑   ↑   ↑
+               i-1  i   j
+1   2   3   8   6   4   5   7
+ */
+class Solution {
+    public void nextPermutation(int[] nums) {
+        int n = nums.length;
+        if (n <= 1) {
+            return;
+        }
+        for (int i = n - 1; i >= 1; i--) {
+            if (nums[i] > nums[i - 1]) {
+                for (int j = n - 1; j >= i; j--) {
+                    if (nums[j] > nums[i - 1]) {
+                        int temp = nums[j];
+                        nums[j] = nums[i - 1];
+                        nums[i - 1] = temp;
+                        Arrays.sort(nums, i, n);
+                        return;
+                    }
+                }
+            }
+        }
+        Arrays.sort(nums);
+    }
+}
