LeetCode 31 Next Permutation 全解析从 O(n!) 暴力枚举到 O(n) 贪心双指针【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 经典中等题Next Permutation下一个排列展开系统讲解字典序排列的核心概念、两种解题路径O(n!·n) 暴力枚举与 O(n) 贪心双指针并结合本仓库LeetCode Solutions中的多语言实现与关联题解给出可复制、可运行的完整代码。读完本文你将掌握如何就地in-place求出字典序下一个排列的标准算法并理解为什么贪心解法是唯一可行的工程化方案。1. 前置知识Prerequisites在动手解决本题之前建议先熟练以下三块基础能力它们也是后续贪心解法的直接工具数组操作Array Manipulation能够熟练进行就地交换swap与子数组反转reverse双指针技术Two Pointers Technique使用左右指针相向移动来反转子数组字典序Lexicographic Ordering理解序列之间如何按字典序比较和排序——这与字符串按字符顺序比较的规则完全一致。字典序的直观含义把数组视为一个数字/字符串从左到右逐位比较第一个出现差异的位置决定大小。例如[1, 2, 3] [1, 3, 2]因为第二位2 3。下一个排列指的就是在所有排列的字典序排序中紧跟当前排列之后的那一个如果当前已是最大排列则回到最小排列即升序排列。提示本仓库的 articles/permutations.md 与 articles/permutations-ii.md 详细讲解了全排列的生成含去重是理解本文暴力法的基础java/0046-permutations.java 与 java/0047-permutations-ii.java 给出了对应源码。2. 解法一暴力法Brute Force2.1 直觉Intuition最直接的想法是生成数组的全部排列按字典序排序在排序结果中找到当前排列的位置返回其后一个排列如果当前已是最后一个排列则回绕wrap around到第一个排列。这种方法的优点是概念上完全忠实于下一个排列的定义缺点是极其低效——排列数量是 n!对稍大的 n 就会爆炸因此它仅用于帮助理解题意实际竞赛与工程中不可用。2.2 算法步骤Algorithm生成输入数组的全部唯一排列将这些排列按字典序排序在有序列表中找到当前数组的位置返回列表中的下一个排列若已到末尾则回绕到第一个将结果拷贝回原数组满足题目就地修改的要求。2.3 多语言实现以下实现均在生成排列时通过跳过重复值来保证唯一性排序后逐个比对当前数组class Solution: def nextPermutation(self, nums: List[int]) - None: Do not return anything, modify nums in-place instead. permutations self.permute(nums[:]) permutations.sort() for i, p in enumerate(permutations): if p nums: nextP permutations[(i 1) % len(permutations)] for j in range(len(nums)): nums[j] nextP[j] break def permute(self, nums: List[int]) - List[List[int]]: res [] def dfs(i): if i len(nums): res.append(nums.copy()) return for j in range(i, len(nums)): if j i and nums[i] nums[j]: continue nums[i], nums[j] nums[j], nums[i] dfs(i 1) for j in range(len(nums) - 1, i, -1): nums[j], nums[i] nums[i], nums[j] nums.sort() dfs(0) return respublic class Solution { public void nextPermutation(int[] nums) { ListListInteger perms permute(nums.clone()); Collections.sort(perms, (a, b) - { for (int i 0; i a.size(); i) { int diff a.get(i) - b.get(i); if (diff ! 0) return diff; } return 0; }); for (int i 0; i perms.size(); i) { ListInteger p perms.get(i); boolean match true; for (int j 0; j nums.length; j) { if (p.get(j) ! nums[j]) { match false; break; } } if (match) { ListInteger next perms.get((i 1) % perms.size()); for (int j 0; j nums.length; j) { nums[j] next.get(j); } return; } } } private ListListInteger permute(int[] nums) { ListListInteger res new ArrayList(); Arrays.sort(nums); boolean[] used new boolean[nums.length]; ListInteger path new ArrayList(); dfs(nums, used, path, res); return res; } private void dfs(int[] nums, boolean[] used, ListInteger path, ListListInteger res) { if (path.size() nums.length) { res.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { if (used[i]) continue; if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; used[i] true; path.add(nums[i]); dfs(nums, used, path, res); path.remove(path.size() - 1); used[i] false; } } }class Solution { public: void nextPermutation(vectorint nums) { auto perms permute(nums); sort(perms.begin(), perms.end()); for (int i 0; i perms.size(); i) { if (perms[i] nums) { auto next perms[(i 1) % perms.size()]; nums next; return; } } } private: vectorvectorint permute(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint res; vectorint path; vectorbool used(nums.size(), false); functionvoid() dfs []() { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; used[i] true; path.push_back(nums[i]); dfs(); path.pop_back(); used[i] false; } }; dfs(); return res; } };class Solution { /** * param {number[]} nums * return {void} Do not return anything, modify nums in-place instead. */ nextPermutation(nums) { const permute (arr) { const res []; arr.sort((a, b) a - b); const used Array(arr.length).fill(false); const path []; const dfs () { if (path.length arr.length) { res.push([...path]); return; } for (let i 0; i arr.length; i) { if (used[i]) continue; if (i 0 arr[i] arr[i - 1] !used[i - 1]) continue; used[i] true; path.push(arr[i]); dfs(); path.pop(); used[i] false; } }; dfs(); return res; }; const perms permute([...nums]); perms.sort((a, b) { for (let i 0; i a.length; i) { if (a[i] ! b[i]) return a[i] - b[i]; } return 0; }); for (let i 0; i perms.length; i) { const p perms[i]; if (p.every((v, j) v nums[j])) { const next perms[(i 1) % perms.length]; for (let j 0; j nums.length; j) { nums[j] next[j]; } break; } } } }public class Solution { public void NextPermutation(int[] nums) { var perms Permute((int[])nums.Clone()); perms.Sort((a, b) { for (int i 0; i a.Count; i) { int diff a[i] - b[i]; if (diff ! 0) return diff; } return 0; }); for (int i 0; i perms.Count; i) { var p perms[i]; bool match true; for (int j 0; j nums.Length; j) { if (p[j] ! nums[j]) { match false; break; } } if (match) { var next perms[(i 1) % perms.Count]; for (int j 0; j nums.Length; j) { nums[j] next[j]; } return; } } } private ListListint Permute(int[] nums) { Array.Sort(nums); var res new ListListint(); var used new bool[nums.Length]; var path new Listint(); void Dfs() { if (path.Count nums.Length) { res.Add(new Listint(path)); return; } for (int i 0; i nums.Length; i) { if (used[i]) continue; if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; used[i] true; path.Add(nums[i]); Dfs(); path.RemoveAt(path.Count - 1); used[i] false; } } Dfs(); return res; } }func nextPermutation(nums []int) { perms : permute(append([]int{}, nums...)) sort.Slice(perms, func(a, b int) bool { for i : 0; i len(perms[a]); i { if perms[a][i] ! perms[b][i] { return perms[a][i] perms[b][i] } } return false }) for i : 0; i len(perms); i { match : true for j : 0; j len(nums); j { if perms[i][j] ! nums[j] { match false break } } if match { next : perms[(i1)%len(perms)] copy(nums, next) return } } } func permute(nums []int) [][]int { sort.Ints(nums) var res [][]int used : make([]bool, len(nums)) var path []int var dfs func() dfs func() { if len(path) len(nums) { res append(res, append([]int{}, path...)) return } for i : 0; i len(nums); i { if used[i] { continue } if i 0 nums[i] nums[i-1] !used[i-1] { continue } used[i] true path append(path, nums[i]) dfs() path path[:len(path)-1] used[i] false } } dfs() return res }class Solution { fun nextPermutation(nums: IntArray) { val perms permute(nums.clone()) perms.sortWith { a, b - for (i in a.indices) { if (a[i] ! b[i]) returnsortWith a[i] - b[i] } 0 } for (i in perms.indices) { var match true for (j in nums.indices) { if (perms[i][j] ! nums[j]) { match false break } } if (match) { val next perms[(i 1) % perms.size] for (j in nums.indices) { nums[j] next[j] } return } } } private fun permute(nums: IntArray): MutableListIntArray { nums.sort() val res mutableListOfIntArray() val used BooleanArray(nums.size) val path mutableListOfInt() fun dfs() { if (path.size nums.size) { res.add(path.toIntArray()) return } for (i in nums.indices) { if (used[i]) continue if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue used[i] true path.add(nums[i]) dfs() path.removeAt(path.size - 1) used[i] false } } dfs() return res } }class Solution { func nextPermutation(_ nums: inout [Int]) { var perms permute(nums) perms.sort { a, b in for i in 0..a.count { if a[i] ! b[i] { return a[i] b[i] } } return false } for i in 0..perms.count { var match true for j in 0..nums.count { if perms[i][j] ! nums[j] { match false break } } if match { let next perms[(i 1) % perms.count] for j in 0..nums.count { nums[j] next[j] } return } } } private func permute(_ nums: [Int]) - [[Int]] { var nums nums.sorted() var res [[Int]]() var used Array(repeating: false, count: nums.count) var path [Int]() func dfs() { if path.count nums.count { res.append(path) return } for i in 0..nums.count { if used[i] { continue } if i 0 nums[i] nums[i - 1] !used[i - 1] { continue } used[i] true path.append(nums[i]) dfs() path.removeLast() used[i] false } } dfs() return res } }impl Solution { pub fn next_permutation(nums: mut Veci32) { let perms Self::permute(nums.clone()); let mut perms perms; perms.sort(); for i in 0..perms.len() { if perms[i] *nums { let next perms[(i 1) % perms.len()]; nums.copy_from_slice(next); return; } } } fn permute(nums: Veci32) - VecVeci32 { let mut nums nums; nums.sort(); let mut res Vec::new(); let mut used vec![false; nums.len()]; let mut path Vec::new(); fn dfs(nums: [i32], used: mut Vecbool, path: mut Veci32, res: mut VecVeci32) { if path.len() nums.len() { res.push(path.clone()); return; } for i in 0..nums.len() { if used[i] { continue; } if i 0 nums[i] nums[i - 1] !used[i - 1] { continue; } used[i] true; path.push(nums[i]); dfs(nums, used, path, res); path.pop(); used[i] false; } } dfs(nums, mut used, mut path, mut res); res } }仓库佐证暴力反复调用 nextPermutation的思路在 java/0060-permutation-sequence.java 的注释中有直接体现——该题第 k 个排列的暴力解法即是从升序排列开始连续调用 nextPermutation k-1 次注释明确标注similar to Next Permutation problem no.31并指出该做法会超时TLE。2.4 复杂度分析Time Space Complexity时间复杂度O(n! · n)—— 生成 n! 个排列每个排列排序/比对需要 O(n)空间复杂度O(n! · n)—— 需要存储全部排列。显然任何超出玩具规模n ≥ 10 左右的输入都会让该方案不可行因此必须转向下一节的贪心解法。3. 解法二贪心 双指针Greedy3.1 直觉Intuition要得到字典序下一个更大的排列需要做能让数组值增大的最小改动。核心洞察是找到最靠右的、能够增大的位置。从右向左扫描找到第一个比其右侧邻居小的元素记为pivot。由于pivot右侧是一个最长递减后缀pivot是唯一可以变大以产生更大排列的位。接着在pivot右侧找到大于 pivot 的最小元素与之交换——这样既保证变大又保证增量最小。交换之后pivot右侧原本是递减序列为了让从 pivot 位开始的新排列尽可能小需要把该后缀反转成升序。若从头到尾都不存在这样的pivot整个数组为递减序列即最大排列则把整个数组反转得到最小排列满足题目的回绕要求。3.2 算法步骤Algorithm从倒数第二个元素向左扫描找到第一个满足nums[i] nums[i1]的下标i若存在这样的i从最右侧向左扫描找到第一个满足nums[j] nums[i]的下标j交换nums[i]与nums[j]反转子数组nums[i1 .. n-1]。以[1, 2, 3]为例找到pivot 1nums[1]2 nums[2]3右侧大于 2 的最小元素是 3交换得[1, 3, 2]后缀[2]反转后仍为[2]结果[1, 3, 2]与字典序一致。以[3, 2, 1]为例无 pivot直接整体反转得[1, 2, 3]正确回绕到最小排列。3.3 多语言实现class Solution: def nextPermutation(self, nums: list[int]) - None: Do not return anything, modify nums in-place instead. n len(nums) i n - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: j n - 1 while nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] l, r i 1, n - 1 while l r: nums[l], nums[r] nums[r], nums[l] l 1 r - 1public class Solution { public void nextPermutation(int[] nums) { int n nums.length; int i n - 2; while (i 0 nums[i] nums[i 1]) { i--; } if (i 0) { int j n - 1; while (nums[j] nums[i]) { j--; } swap(nums, i, j); } int l i 1, r n - 1; while (l r) { swap(nums, l, r--); } } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }class Solution { public: void nextPermutation(vectorint nums) { int n nums.size(); int i n - 2; while (i 0 nums[i] nums[i 1]) { i--; } if (i 0) { int j n - 1; while (nums[j] nums[i]) { j--; } swap(nums[i], nums[j]); } int l i 1, r n - 1; while (l r) { swap(nums[l], nums[r--]); } } };class Solution { /** * param {number[]} nums * return {void} Do not return anything, modify nums in-place instead. */ nextPermutation(nums) { const n nums.length; let i n - 2; while (i 0 nums[i] nums[i 1]) { i--; } if (i 0) { let j n - 1; while (nums[j] nums[i]) { j--; } [nums[i], nums[j]] [nums[j], nums[i]]; } let l i 1, r n - 1; while (l r) { [nums[l], nums[r]] [nums[r], nums[l]]; l; r--; } } }public class Solution { public void NextPermutation(int[] nums) { int n nums.Length; int i n - 2; while (i 0 nums[i] nums[i 1]) { i--; } if (i 0) { int j n - 1; while (nums[j] nums[i]) { j--; } Swap(nums, i, j); } int l i 1, r n - 1; while (l r) { Swap(nums, l, r--); } } private void Swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }func nextPermutation(nums []int) { n : len(nums) i : n - 2 for i 0 nums[i] nums[i1] { i-- } if i 0 { j : n - 1 for nums[j] nums[i] { j-- } nums[i], nums[j] nums[j], nums[i] } l, r : i1, n-1 for l r { nums[l], nums[r] nums[r], nums[l] l r-- } }class Solution { fun nextPermutation(nums: IntArray) { val n nums.size var i n - 2 while (i 0 nums[i] nums[i 1]) { i-- } if (i 0) { var j n - 1 while (nums[j] nums[i]) { j-- } nums[i] nums[j].also { nums[j] nums[i] } } var l i 1 var r n - 1 while (l r) { nums[l] nums[r].also { nums[r] nums[l] } l r-- } } }class Solution { func nextPermutation(_ nums: inout [Int]) { let n nums.count var i n - 2 while i 0 nums[i] nums[i 1] { i - 1 } if i 0 { var j n - 1 while nums[j] nums[i] { j - 1 } nums.swapAt(i, j) } var l i 1 var r n - 1 while l r { nums.swapAt(l, r) l 1 r - 1 } } }impl Solution { pub fn next_permutation(nums: mut Veci32) { let n nums.len(); let mut i n as i32 - 2; while i 0 nums[i as usize] nums[i as usize 1] { i - 1; } if i 0 { let mut j n - 1; while nums[j] nums[i as usize] { j - 1; } nums.swap(i as usize, j); } nums[(i as usize 1)..].reverse(); } }3.4 复杂度分析Time Space Complexity时间复杂度O(n)—— 三次线性扫描找 pivot、找交换位、反转后缀每步至多遍历一次数组空间复杂度O(1)—— 完全就地修改仅使用常数个额外变量。这也是该题在工程上的标准答案一次遍历定位、一次交换、一次反转与 C 标准库std::next_permutation的实现思路一致。4. 常见陷阱Common Pitfalls即便掌握了贪心框架实现时仍有三处极易出错尤其涉及重复元素时必须格外小心。4.1 用错误的比较方式找 Pivotpivot 必须是最靠右的、小于其右邻居的元素即严格满足nums[i] nums[i1]。如果在寻找时误用写成nums[i] nums[i1]才停下算法会在含重复元素的数组上失效——它会跳过合法的 pivot 位置导致无法得到正确的下一个排列。关键在于递减后缀允许相等因此必须用严格小于来判断 pivot 的终止条件。4.2 交换了错误的元素找到 pivot 之后必须与其右侧所有大于 pivot 的元素中最小者交换。如果改成从左侧起找到的第一个更大元素进行交换虽然排列变大了但不是字典序上最小的增量会跳过若干合法排列。正确做法是从最右端向左扫描第一个满足nums[j] nums[i]的元素就是大于 pivot 的最小者因为后缀是递减的。4.3 忘记反转后缀交换完成后pivot 右侧的后缀仍是递减顺序。如果不把它反转成升序得到的排列会比真正下一个排列更大。反转后缀是得到最小的更大排列的关键一步与回绕到最小排列整体反转在原理上完全一致降序是字典序最大升序是字典序最小。5. 总结与仓库延伸阅读本文完整覆盖了 Next Permutation 的两种解法O(n!·n) 的暴力枚举与 O(n) 的贪心双指针后者通过定位 pivot → 交换最小更大元素 → 反转后缀三步即可就地完成且天然兼容重复元素。需要特别记住的边界是当数组整体降序已是最大排列时直接反转整个数组回到升序最小排列。若想进一步巩固排列类问题的整体体系可继续阅读本仓库的以下资源articles/permutations.md无重复元素全排列的生成与回溯框架articles/permutations-ii.md含重复元素时的去重剪枝技巧articles/permutation-string.md排列在子串匹配滑动窗口中的应用java/0060-permutation-sequence.java第 k 个排列的数学解法其注释展示了与本题暴力法的直接关联articles/next-permutation.md本篇的原始题解文档含全部多语言实现。掌握了下一个排列这一原子操作你就可以进一步解决第 k 个排列、全排列、排列字符串匹配等一系列字典序与排列问题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考