游戏网站代码_广州安全教育平台账号是多少_网站优化策略分析论文_开网店怎么推广运营

LeetCode 31 - 下一个排列 是一个经典题，考察对排列的基本操作，包括逆序、排序以及贪心思想。该题目常会出现在竞赛、面试中，变体场景也非常多，例如字典序排列的生成、排列搜索问题等。以下是详细解法、分析以及变体分类。

---

题目描述

实现获取下一个排列的算法，该排列是字典序中比当前排列大的下一个排列。

• 如果没有更大的排列，则将其排列为最小（即升序）。
• 必须在 原地修改，并且只允许使用额外常数空间。

示例

输入: nums = [1,2,3]
输出: [1,3,2]
解释: 下一个排列是 [1,3,2]。输入: nums = [3,2,1]
输出: [1,2,3]
解释: 排列 [3,2,1] 是最大的，返回最小排列 [1,2,3]。输入: nums = [1,1,5]
输出: [1,5,1]
解释: 下一个排列是 [1,5,1]。

---

重要分析

• 字典序排列：为给定排列找到下一个字典序的排列。
• 关键观察：
  1. 要获得字典序 更大的排列，需要在数组中找到一个 较小的数和较大的数交换。
  2. 交换后，要让剩余的部分尽可能小（排列最小化）。
  3. 若当前排列是最大序列（例如降序排列），返回最小序列（升序排列）。

---

解法及模板

解法 1：两指针 + 局部调整

思路

1. 从右向左查找破坏升序的位置：
   • 找到第一个下降的位置 i，使得 nums[i] < nums[i+1]。
   • 如果找不到，说明当前序列是降序排列，直接将整个数组反转（即为最小排列）。
2. 从右向左寻找比 nums[i] 大的最小元素：
   • 从右向左扫描，找到第一个 nums[j] > nums[i] 的位置 j。
   • 交换 nums[i] 和 nums[j]。
3. 反转 i+1 到数组末尾的子数组：
   • 使交换后的尾部部分变为升序，以形成“字典序最小”的排列。

模板代码

class Solution {public void nextPermutation(int[] nums) {int n = nums.length;int i = n - 2;// Step 1: 找到第一个下降的位置 iwhile (i >= 0 && nums[i] >= nums[i + 1]) {i--;}// Step 2: 如果找到 i，寻找比 nums[i] 大的最小数if (i >= 0) {int j = n - 1;while (j >= 0 && nums[j] <= nums[i]) {j--;}swap(nums, i, j); // 交换}// Step 3: 反转 i+1 到末尾的部分reverse(nums, i + 1, n - 1);}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}private void reverse(int[] nums, int start, int end) {while (start < end) {swap(nums, start, end);start++;end--;}}
}

复杂度分析

• 时间复杂度: O(n)
  • 找第一个下降点：需要 O(n)。
  • 找较大数的交换：需要 O(n)。
  • 最后反转子数组：需要 O(n)。
• 空间复杂度: O(1)，原地操作，无需额外空间。

---

解法 2：全排列生成（暴力法）

思路

• 如果直接想到暴力法，可以生成当前排列的所有全排列，找到当前排列的 下一个排列。
• 代码通常通过递归生成所有排列。
• 显然此方法不符合题目要求，仅作为理论对比。

---

解法 3：基于排序

思路

• 类似于暴力法，尝试找到所有排列的方式并排序。找到当前排列的位置索引，然后返回其下一个排列。
• 时间复杂度远高于 O(n)。一般来说只是一种思想验证。

---

经典变体

变体 1：寻找第 K 个排列

问题背景：给定整数 n，代表 1~n 的数字，要求返回第 k 小的排列（字典序排列）。

思路

1. 全排列数规律：n! / (n-1)! 的特性可以分配每个子集的数量。
2. 比如：n=3：
   • 1xxx 有 2! 个排列。
   • 2xxx 有 2! 个排列，以此类推。
3. 通过减去 k 的方式加入递归解决。

模板代码

class Solution {public String getPermutation(int n, int k) {List<Integer> nums = new ArrayList<>();for (int i = 1; i <= n; i++) nums.add(i); // 初始化数组int[] fact = new int[n + 1]; // 阶乘数组fact[0] = 1;for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i; // 计算阶乘k--; // 调整为 0 索引顺序StringBuilder result = new StringBuilder();for (int i = 1; i <= n; i++) {int index = k / fact[n - i];result.append(nums.get(index)); // 确定位置nums.remove(index); // 移除被选中的数字k %= fact[n - i]; // 剩余部分}return result.toString();}
}

复杂度

• 时间复杂度: O(n²)
  • 阶乘计算 O(n)。
  • 构建排列 O(n²)。
• 空间复杂度: O(n)，用于保存数字列表。

---

变体 2：判断一个排列是否为回文排列

问题背景：给定一个整数数组，判断它的排列是否为回文排列。

思路

• 一个排列可以被排成回文当且仅当：
  1. 除了中间一个字符外的其他字符，必须出现偶数次。
  2. 如果出现了两个以上奇数次的字符，则不能组成回文。

---

变体 3：前一个排列

问题背景：获取给定排列的前一个字典序排列。

思路

• 思路与原题相似：
  1. 找到第一个 升序 的位置（从右向左）。
  2. 找到比 nums[i] 小的 最大数。
  3. 交换 nums[i] 和这个数后，反转右侧部分。

---

变体 4：所有数字的全排列

问题背景：生成当前数字的所有可能排列。

思路

使用回溯法生成全排列：

1. 逐位填入数字。
2. 递归生成剩余数字的排列。
3. 回溯时，复原原数组状态。

模板代码

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();backtrack(nums, new ArrayList<>(), result, new boolean[nums.length]);return result;}private void backtrack(int[] nums, List<Integer> temp, List<List<Integer>> result, boolean[] used) {if (temp.size() == nums.length) {result.add(new ArrayList<>(temp));return;}for (int i = 0; i < nums.length; i++) {if (!used[i]) {used[i] = true;temp.add(nums[i]);backtrack(nums, temp, result, used);temp.remove(temp.size() - 1);used[i] = false;}}}
}

复杂度

• 时间复杂度: O(n!)，完整排列生成。
• 空间复杂度: O(n)，递归栈深度。

---

快速 AC 总结

1. 熟记主解法：
   • 下一个排列的模板需牢记：找到位置 i 和 j，交换 + 反转。
2. 变体泛化能力：
   • 对前一个排列、全排列生成，通过构造/递归等方式解决。
   • 与排序相关的子问题，优先考虑类似的贪心或递归做法。
3. 模板快速迁移：
   • 面试或竞赛题目中，变体往往基于“字典序”思想，熟悉排序和定位相关问题的原理非常重要。