- 正确答案：下一个排列（Next Permutation）是指在字典序中紧接当前排列之后的最小排列。例如，[1,2,3] 的下一个排列是 [1,3,2]；[3,2,1] 是字典序最大排列，其下一个排列为 [1,2,3]（即循环回到最小排列）。算法需原地修改数组，时间复杂度 O(n)，空间复杂度 O(1)。 - 解答思路：该问题本质是找字典序中“刚好更大”的排列，不能暴力生成所有排列（代价太高）。关键观察是：字典序增长依赖于从右向左寻找第一个“可提升位置”——即第一个满足 nums[i] < nums[i+1] 的索引 i（从右往左扫描），该位置是能通过交换变大的最右边界。找到后，在 i 右侧（已严格递减）中找最小的、但大于 nums[i] 的元素 nums[j]（因右侧递减，可从右往左第一个满足 nums[j] > nums[i] 的 j 即为所求）。交换 nums[i] 和 nums[j] 后，i 右侧子数组仍保持递减，而我们希望它变为字典序最小（即递增），故只需将其反转即可。整个过程分三步：① 从右向左找第一个升序对的左下标 i；② 从右向左找第一个大于 nums[i] 的下标 j；③ 交换 i 和 j，再反转 i+1 到末尾的子数组。 - 深度知识讲解：本题考察对字典序结构的深刻理解与线性扫描优化能力。字典序比较本质是前缀决定性：两个排列 a 和 b，首个不同位置 k 决定大小，若 a[k] < b[k] 则 a < b。因此，“下一个”必须尽可能保持长前缀不变，仅在最靠右的可调整位置做最小改动。这直接导出算法的三步逻辑。底层依赖数组的局部有序性：当从右往左首次遇到 nums[i] < nums[i+1]，说明 nums[i+1..n-1] 是严格递减的（否则更早就会出现升序对），即该后缀已是字典序最大的排列；因此要增大整体，必须修改 nums[i]，且应换一个略大于它的值（贪心选择最小可行值以保证“下一个”），而因后缀递减，从右往左第一个大于 nums[i] 的元素即为最小可行替换值。最后反转后缀是因为：交换后，nums[i+1..n-1] 仍保持递减（因 nums[j] 是第一个大于 nums[i] 的，而 j 右侧都 ≤ nums[i] < nums[j]，且原递减，故 j 右侧仍 ≤ nums[j]，但需注意：交换后，nums[i+1..n-1] 整体是否仍递减？实际上不一定，但关键点在于：原后缀 nums[i+1..n-1] 递减，且 nums[j] 是其中大于 nums[i] 的最小元素，那么交换后，新后缀为 nums[i+1..j-1] + nums[i] + nums[j+1..n-1]，此时 nums[i+1..j-1] ≥ nums[j] > nums[i]，且 nums[j+1..n-1] ≤ nums[i]（因原序列递减且 nums[j] 是第一个 > nums[i] 的），故新后缀是“高—低”结构，但并非单调。然而，我们并不需要维持单调性，而是要让后缀变成字典序最小——而字典序最小的排列就是升序排列。由于原后缀是降序，其升序恰好是其反转，故反转即得最小可能后缀。该操作的正确性可由数学归纳或置换群中相邻换位生成序列的性质支撑。此外，该算法是 STL 中 std::next_permutation 的标准实现，广泛用于组合枚举、密码学测试用例生成等场景。注意：该算法不适用于含重复元素的排列（如 [1,1,2]），因字典序定义仍成立，但题目通常默认无重；若有重，需额外跳过相等元素避免重复排列，此时 j 的查找需改为 while (j > i && nums[j] <= nums[i]) j--，确保严格大于。 - 伪代码： ``` function nextPermutation(nums): n = length(nums) // 步骤1：从右往左找第一个 i，使得 nums[i] < nums[i+1] i = n - 2 while i >= 0 and nums[i] >= nums[i + 1]: i = i - 1 // 若找不到，说明整个数组递减，已是最大排列，直接反转成最小 if i < 0: reverse(nums, 0, n - 1) return // 步骤2：从右往左找第一个 j，使得 nums[j] > nums[i] j = n - 1 while j > i and nums[j] <= nums[i]: j = j - 1 // 步骤3：交换 nums[i] 和 nums[j] swap(nums[i], nums[j]) // 步骤4：反转 i+1 到末尾的子数组 reverse(nums, i + 1, n - 1) function reverse(arr, left, right): while left < right: swap(arr[left], arr[right]) left = left + 1 right = right - 1 function swap(a, b): temp = a a = b b = temp ``` - 补充说明：该算法的每一步都是不可省略的。例如，若跳过反转（步骤4），则后缀仍是局部较大排列，无法保证“下一个”。时间复杂度：两次扫描 O(n)，一次反转 O(n)，总体 O(n)；空间复杂度：仅用常数额外变量，O(1)。边界情况包括：空数组、单元素（直接返回）、全相同元素（如 [1,1,1]，此时 i 找不到，执行反转，结果不变，符合预期）。面试中若被问及“为什么不是用 next_permutation 库函数”，应回答：考察对字典序构造原理和原地变换能力的理解，而非调包能力；且实际工程中可能需定制逻辑（如带约束的排列生成）。

xtransfer一面（Java社招）

全站热榜

创作者周榜