leetcode 31 python
时间: 2025-04-27 12:21:26 浏览: 13
### LeetCode Problem 31 Next Permutation 的 Python 实现
对于LeetCode上的第31题——Next Permutation,目标是在不使用额外空间的情况下找到给定序列的下一个排列组合。如果不存在更大的排列,则重新排列数组为最小的排列(即升序)。此问题可以通过特定算法来解决。
为了实现该功能,可以遵循以下逻辑:
- 首先从右向左遍历列表,寻找第一个违反降序规则的位置 `i`。
- 接着再次从右向左扫描,在位置 `i` 右侧的部分里找出刚好大于 `nums[i]` 的数并交换两者。
- 最后反转 `i` 后面所有的元素顺序[^1]。
下面是具体的Python代码实现方式:
```python
def nextPermutation(nums):
n = len(nums)
# Step 1: Find the first decreasing element from end
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
# Step 2: Find successor to pivot
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# Swap elements at index 'i' & 'j'
nums[i], nums[j] = nums[j], nums[i]
# Step 3: Reverse suffix starting beyond position 'i'
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
```
上述方法能够有效地解决问题,并且满足题目要求的空间复杂度 O(1),时间复杂度最坏情况下为O(n)。
阅读全文
相关推荐

















