作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
问题描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须原地修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3] 输出：[1,3,2]
示例 2：
输入：nums = [3,2,1] 输出：[1,2,3]
示例 3：
输入：nums = [1,1,5] 输出：[1,5,1]
1.单遍扫描
这个问题是典型的计算组合问题中的“下一个排列”配置，其目标是在字典序的规则下找到当前排列的下一个排列。核心思路可以总结为以下几步：
- 从右向左查找第一个升序的元素对：即找到第一个
nums[k] < nums[k+1]的位置k。这意味着从k+1到end的序列是降序的。 - 在
nums[k+1]到nums[end]中找到比nums[k]大的最小元素：这个元素与nums[k]交换。 - 将
nums[k+1]到nums[end]排序为升序：实际上由于它们原来是降序的，所以只需将其翻转。
这种方法利用了字典序排列的性质，通过局部操作实现全局字典序的递增。
代码示例
def nextPermutation(nums): i = len(nums) - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i >= 0: j = len(nums) - 1 while nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i] # 交换 # 翻转i之后的部分 left, right = i + 1, len(nums) - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left, right = left + 1, right - 1 # 测试代码 nums1 = [1,2,3] nextPermutation(nums1) print(nums1) # Output: [1,3,2] nums2 = [3,2,1] nextPermutation(nums2) print(nums2) # Output: [1,2,3] nums3 = [1,1,5] nextPermutation(nums3) print(nums3) # Output: [1,5,1]
算法分析
- 时间复杂度：O(n)，其中 n 是列表的长度。算法中有两个主要的线性阶段：寻找
i和j，以及反转子数组。 - 空间复杂度：O(1)，原地修改数组，不使用额外的存储空间。
2.全排列的递归生成
虽然此方法对于实际编程竞赛或面试来说效率可能不高，它提供了一种理解问题的框架，特别是在理解如何构造所有排列时。该方法依赖于递归生成所有排列，并在过程中检测到当前排列，然后返回下一个。
实现思路：
- 生成所有排列：使用递归函数按字典顺序生成数组的所有排列。
- 检测当前排列：在生成的过程中，当发现当前排列时，取下一次递归所生成的排列作为结果。
- 效率问题：这种方法将会生成数组的所有排列，直到找到当前排列的下一个，因此在最坏的情况下，其效率是非常低的（尤其是当数组大且接近最大排列时，如
[3, 2, 1]）。
代码示例
def nextPermutation(nums): def generate_permutations(n, A): if n == 1: yield A[:] else: for i in range(n - 1): yield from generate_permutations(n - 1, A) j = 0 if n % 2 == 0 else i A[j], A[n - 1] = A[n - 1], A[j] yield from generate_permutations(n - 1, A) found = False prev = None for perm in generate_permutations(len(nums), nums[:]): if found: nums[:] = perm return if perm == nums: found = True prev = perm if not found or prev == nums: nums.sort() # 测试代码 nums1 = [1,2,3] nextPermutation(nums1) print(nums1) # Output: [1,3,2] nums2 = [3,2,1] nextPermutation(nums2) print(nums2) # Output: [1,2,3] nums3 = [1,1,5] nextPermutation(nums3) print(nums3) # Output: [1,5,1]
算法分析
- 时间复杂度：O(N!)，其中 N 是数组长度。递归生成排列的过程需要遍历所有可能的排列。
- 空间复杂度：O(N)，主要是递归栈空间的使用以及排列存储的空间。
3.直接模拟寻找和交换过程
这种方法仍然基于观察到的排列性质，即通过确定翻转的边界来模拟生成下一个排列的过程。
实现思路：
- 从后向前查找第一个递减元素：寻找第一个满足
nums[k] < nums[k+1]的k，这意味着从nums[k+1]到nums[end]必然是降序。 - 从后向前查找第一个大于
nums[k]的元素：从序列的末尾向前查找，找到第一个大于nums[k]的元素nums[l]。 - 交换
nums[k]和nums[l]：交换这两个元素后，nums[k+1]到nums[end]仍然保持降序。 - 翻转
nums[k+1]到nums[end]：将这部分序列翻转，使其变为升序，这是因为需要找到比当前排列稍大的下一个排列。
代码示例
def nextPermutation(nums): n = len(nums) if n <= 1: return # Step 1: Find the largest index k such that nums[k] < nums[k + 1] k = n - 2 while k >= 0 and nums[k] >= nums[k + 1]: k -= 1 if k >= 0: # A valid k found # Step 2: Find the largest index l greater than k such that nums[k] < nums[l] l = n - 1 while nums[l] <= nums[k]: l -= 1 # Step 3: Swap nums[k] and nums[l] nums[k], nums[l] = nums[l], nums[k] # Step 4: Reverse from k + 1 to end nums[k + 1:] = reversed(nums[k + 1:]) # Example usage nums = [1, 2, 3] nextPermutation(nums) print(nums) # Output: [1, 3, 2] nums = [3, 2, 1] nextPermutation(nums) print(nums) # Output: [1, 2, 3] nums = [1, 1, 5] nextPermutation(nums) print(nums) # Output: [1, 5, 1]
算法分析
- 时间复杂度：O(N)。尽管在寻找
k和l的时候各自需要 O(N) 的时间，以及翻转需要 O(N/2)，整体操作仍视为 O(N)。 - 空间复杂度：O(1)。所有操作都是在原数组上进行的，不需要额外空间。
总结
- 单遍扫描法：通过从后向前扫描，找到逆序的断点，进行交换和翻转，直观高效，是标准解法。
- 递归全排列法：生成所有排列直到当前排列之后的排列，理解深入但效率低，不适合实际应用。
- 模拟寻找和交换过程：基于数学的直接寻找并模拟交换的过程，操作简单明了，易于理解和实现。
这三种方法从实用性和教学价值两个角度提供了不同的解决策略，其中单遍扫描法因其效率和简洁性最为推荐。
欢迎关注微信公众号 数据分析螺丝钉
