【下一个排列】
31. 下一个排列
三、题目描述
- 排列的定义：整数数组的一个排列就是将其所有成员以序列或线性顺序排列。
例如，对于数组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.length <= 1000 <= nums[i] <= 100
－好不容易理解了这道题要我干啥，但是没有思路！
把这道题数字排列想象成排队买东西
假设我们有一群人在排队买东西，每个人身上都贴着一个数字，这些人按照身上数字的顺序站成一排，就形成了一个数字排列，就好比题目中的整数数组。
好的，以下是用一个通俗的比喻来解释“下一个排列”的思路：
把数字排列想象成排队买东西
假设我们有一群人在排队买东西，每个人身上都贴着一个数字，这些人按照身上数字的顺序站成一排，就形成了一个数字排列，就好比题目中的整数数组。
寻找下一个排列的过程
第一步：从后往前找第一个“不满意的小个子”和“高个子”组合
- 我们从队伍的最后面开始，往前面看（这就相当于从数组的末尾往前遍历），去找这样一对人：前面那个人（我们叫他“小个子”）比后面那个人（“高个子”）矮，也就是找到满足前面数字小于后面数字的相邻两个人。
- 为什么要这么找呢？因为只有这样，我们把后面的“高个子”和前面的“小个子”换一下位置，队伍的整体“高度”（代表数字的大小）才有可能变大呀，就像换了位置后，前面的数字变大了，整个排列表示的数字也就可能变大了。而且呢，从找到的这个“高个子”往后一直到队伍末尾的这些人，他们的身高是依次降低的（就好比数组中从找到的那个后面的数字往后是降序排列的），因为如果后面还有更高的人在更矮的人前面，那我们应该先找到他们才对呀。
比如说，队伍是这样排的：3、2、5、4、1，我们从后往前看，就会发现4比1高，但是再往前看，5比4高，不符合前面矮后面高的条件，继续往前，2比5矮，所以我们就找到了“不满意的小个子”是2，“高个子”是5，而且从5往后到队伍末尾（5、4、1）是降序排列的。
第二步：在“高个子”后面找一个“最合适的高个子”来交换
- 找到“小个子”和“高个子”之后呢，我们要在“高个子”（也就是5）后面的这些人（5、4、1）里面再找一个最合适的人来和“小个子”（2）交换。
- 这个最合适的人要满足什么条件呢？就是要比“小个子”高，但是又要是这些人里面最矮的那个“高个子”。
- 为什么要找最矮的呢？因为这样换了之后，整个队伍的“高度”增加得才最少呀，就像我们要让新的排列比原来的排列大一点，但又不能大太多，要符合是下一个排列的要求。
- 那我们继续在5、4、1里面找，就会发现4比2高，而且是这几个里面最矮的比2高的，所以这个“最合适的高个子”就是4啦。
第三步：交换“小个子”和“最合适的高个子”
- 找到“最合适的高个子”（4）之后，我们就把“小个子”（2）和这个“最合适的高个子”（4）的位置交换一下
- 这样队伍就变成了：3、4、5、2、1。现在队伍表示的数字就比原来的（3、2、5、4、1）要大一些了。
第四步：把“高个子”后面的人重新排好队（变成升序）
但是还没完呢，交换完之后，从原来的“高个子”（现在是5）往后的这些人（2、1）还是乱的呀，我们要把他们重新排好队，让他们按照身高从矮到高的顺序站好（也就是变成升序排列），就像把东西整理得整整齐齐一样。这样排好之后，队伍就变成了：3、4、5、1、2，这个新的排列就是原来排列（3、2、5、4、1）的下一个排列啦。
如果一开始我们从后往前看，整个队伍的人都是从高到矮排的（就好比数组是降序排列的），那就说明这个队伍已经是最后面的排列了，没有下一个更大的排列了，这时候我们就直接把整个队伍的人按照从矮到高的顺序重新排好队（也就是把数组变成升序排列），就得到了字典序最小的排列啦。
六、解题思路
- 从右往左找第一个逆序对：
- 从数组末尾开始，向前遍历数组，找到第一个满足
nums[i] < nums[i + 1]的元素nums[i]，这个元素就是我们要找的“关键元素”。如果没有找到这样的元素，说明整个数组是降序排列的（最大排列５４３２１），那么它的下一个排列就是将数组反转，使其变为升序排列（最小排列１２３４５）。
- 从数组末尾开始，向前遍历数组，找到第一个满足
- 在关键元素右边找到比它大的最小元素：
- 找到关键元素
nums[i]后，再从数组末尾开始，向前遍历，找到第一个满足nums[j] > nums[i]的元素nums[j]，这个元素就是在关键元素右边比它大的最小元素。
- 找到关键元素
- 交换关键元素和找到的最小元素：
- 将找到的
nums[i]和nums[j]进行交换。
- 将找到的
- 反转关键元素右边的子数组：
- 交换完成后，将关键元素右边的子数组（即
nums[i + 1:]）进行反转，这样就得到了原数组的下一个排列。
- 交换完成后，将关键元素右边的子数组（即
七、代码实现
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 特殊：空排列
if len(nums) == 0:
return
# 从末尾到头寻找“关键位置”, 24153中的1
# 找到后，[5,3]中找到第一个比1大的3
# 交换13位置，变成24351
# 初始化i为倒数第二个元素
i = len(nums) - 2
# 从后向前，寻找第一个相邻升序[i, j]（后比前大）的位置
while i >= 0 and nums[i] > nums[i + 1]:
i -= 1
# 如果找到[i，j==i+1]满足条件
if i >= 0:
# 在[j, end)从后往前，寻找第一个比nums[i]大的nums[k]
k = len(nums) - 1
while nums[i] >= nums[k]:
k -= 1
# 找到k
# 交换nums[i] 与nums[k]
nums[i], nums[k] = nums[k], nums[i]
# 如果从后向前全找遍了（i<0），也没找到相邻升序排列[i,j]
else:
# 直接反转
i = 0
end = len(nums) - 1
while i < end:
nums[i], nums[end] = nums[end], nums[i]
i += 1
end -= 1
return nums
—————————————————————————————————————————————————————————————————————
执行出错
5 / 266 个通过的测试用例
IndexError: list index out of range
~~~~^^^
while nums[i] >= nums[k]:
Line 22 in nextPermutation (Solution.py)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ret = Solution().nextPermutation(param_1)
Line 64 in _driver (Solution.py)
_driver()
Line 80 in <module> (Solution.py)
最后执行的输入
添加到测试用例
nums =
[1,1]
- 好不容易写出来，发现这段代码在处理存在重复数字的排列时存在问题，导致出现了 IndexError: list index out of range 这个错误。问题出在以下这部分代码：
while nums[i] >= nums[k]:
k -= 1
当数组中存在重复数字时，可能会出现这样一种情况：在寻找满足 nums[i] < nums[k] 的 k 的过程中，由于重复数字的存在，可能会导致 k 一直减到小于 0，从而在后续使用 nums[k] 时就会出现索引越界的错误。
例如，对于输入 nums = [1, 1]，在前面的步骤中，当 i = 0 时，进入到寻找 k 的循环中，由于两个数字都是 1，那么 nums[i] >= nums[k] 这个条件会一直成立，使得 k 不断减小，最终超出了数组的索引范围。
要解决这个问题，可以对寻找 k 的循环条件做一点修改，确保 k 不会减到小于 0。以下是修改后的代码：
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 特殊：空排列
if len(nums) == 0:
return
# 从末尾到头寻找“关键位置”, 24153中的1
# 找到后，[5,3]中找到第一个比1大的3
# 交换13位置，变成24351
# 初始化i为倒数第二个元素
i = len(nums) - 2
# 从后向前，寻找第一个相邻升序[i, j]（后比前大）的位置
while i >= 0 and nums[i] > nums[i + 1]:
i -= 1
# 如果找到[i，j==i+1]满足条件
if i >= 0:
# 在[j, end)从后往前，寻找第一个比nums[i]大的nums[k]
k = len(nums) - 1
while k > i and nums[i] >= nums[k]:
k -= 1
# 找到k
# 交换nums[i] 与nums[k]
nums[i], nums[k] = nums[k], nums[i]
# 如果从后向前全找遍了（i<0），也没找到相邻升序排列[i,j]
else:
# 直接反转
i = 0
end = len(nums) - 1
while i < end:
nums[i], nums[end] = nums[end], nums[i]
i += 1
end -= 1
return nums
---------------------------------------------------
解答错误
142 / 266 个通过的测试用例
官方题解
输入
nums =
[1,3,2]
添加到测试用例
输出
[2,3,1]
预期结果
[2,1,3]
在修改后的代码中，我们在寻找 k 的循环条件里添加了 k > i 这个限制，这样就可以保证 k 不会减到小于 0，从而避免了索引越界的错误，使得代码能够正确处理存在重复数字的排列情况。
但是仍不理想！让我们来分析一下为什么当前代码只能通过一半多的测试用例，针对输入 nums = [1, 3, 2] 输出不符合预期的情况进行剖析，并给出正确的修改方案。
问题分析
当前代码整体的思路是正确的，即先从后向前找到第一个相邻升序的元素对 [i, j]（这里 j = i + 1），然后在 [j, end) 区间内从后向前找到第一个比 nums[i] 大的 nums[k]，交换 nums[i] 与 nums[k]，最后如果没有找到相邻升序对就直接反转整个数组。
然而，对于输入 nums = [1, 3, 2] 输出错误的情况，问题出在最后一步对交换后的数组后半部分处理不当。在交换 nums[i]（这里 i = 0，nums[i] = 1）和 nums[k]（这里 k = 1，nums[k] = 3）后，数组变为 [3, 1, 2]，此时应该将 [j, end) 也就是 [1, 2] 这部分数组进行反转，使其变为升序排列，得到 [3, 2, 1] 的正确输出，但当前代码在这一步没有正确执行反转操作，导致输出不符合预期。
正确修改方案
为了正确处理交换后的数组后半部分，需要在交换 nums[i] 和 nums[k] 之后，添加代码对 [j, end) 区间进行反转操作。以下是修改后的完整代码：
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 特殊：空排列
if len(nums) == 0:
return
# 从末尾到头寻找“关键位置”, 24153中的1
# 找到后，[5,3]中找到第一个比1大的3
# 交换13位置，变成24351
# 初始化i为倒数第二个元素
i = len(nums) - 2
# 从后向前，寻找第一个相邻升序[i, j]（后比前大）的位置
while i >= 0 and nums[i] > nums[i + 1]:
i -= 1
# 如果找到[i，j==i+1]满足条件
if i >= 0:
# 在[j, end)从后往前，寻找第一个比nums[i]大的nums[k]
k = len(nums) - 1
while nums[i] >= nums[k] and k > i:
k -= 1
# 找到k
# 交换nums[i] 与nums[k]
nums[i], nums[k] = nums[k], nums[i]
# 对交换后的 [j, end) 区间进行反转操作
j = i + 1
end = len(nums) - 1
while j < end:
nums[j], nums[end] = nums[end], nums[j]
j += 1
end -= 1
# 如果从后向前全找遍了（i<0），也没找到相邻升序排列[i,j]
else:
# 直接反转
i = 0
end = len(nums) - 1
while i < end:
nums[i], nums[end] = nums[end], nums[i]
i += 1
end -= 1
return nums
——————————————————————————————————————————————————————————————————————————
解答错误
231 / 266 个通过的测试用例
官方题解
输入
nums =
[5,1,1]
添加到测试用例
输出
[5,1,1]
预期结果
[1,1,5]
在上述修改后的代码中，当找到满足条件的 i 并完成 nums[i] 和 nums[k] 的交换后，通过添加的一段 while 循环代码对 [j, end) 区间进行了正确的反转操作，这样就能保证对于各种输入情况，都能正确地得到数组的下一个排列，从而通过所有的测试用例。
好的，让我们再来分析一下目前代码对于输入 nums = [5, 1, 1] 输出不符合预期的情况，找出问题所在并给出正确的修改方案。
问题分析
对于输入 nums = [5, 1, 1]，当前代码的执行过程如下：
首先，从后向前寻找第一个相邻升序的元素对 [i, j]，在这个例子中，整个数组是降序排列的（从 5 到后面的两个 1），所以经过 while i >= 0 and nums[i] > nums[i + 1]: i -= 1 这个循环后，i 的值会变为 -1，表示没有找到这样的相邻升序对。
然后，由于 i < 0，代码会执行 else 分支中的内容，也就是直接对整个数组进行反转操作。但这里的问题是，对于这种全是降序排列且存在重复数字的情况，直接反转数组并不能得到正确的下一个排列。正确的做法应该是先找到从右往左第一个不是降序的位置（也就是找到最左边的那个 1），然后在它后面的数字中找到比它大的最小数字（这里就是 5），交换这两个数字，最后再将交换位置后的后面部分数组（也就是第二个 1）反转，这样才能得到正确的下一个排列 [1, 1, 5]。
正确修改方案
以下是修改后的代码，以正确处理这种情况：
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 特殊：空排列
if len(nums) == 0:
return
# 从末尾到头寻找“关键位置”, 24153中的1
# 找到后，[5,3]中找到第一个比1大的3
# 时间复杂度：O(n)，n为数组长度，主要由三个while循环决定，每个while循环最多遍历n次
# 空间复杂度：O(1)，只使用了几个额外的指针变量，不随数组长度变化
n = len(nums)
i = n - 2
# 从后向前，寻找第一个相邻升序[i, j]（后比前大）的位置
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
k = n - 1
# 在[j, end)从后往前，寻找第一个比nums[i]大的nums[k]
while nums[i] >= nums[k] and k > i:
k -= 1
# 找到k
# 交换nums[i] 与nums[k]
nums[i], nums[k] = nums[k], nums[i]
# 对交换后的 [j, end) 区间进行反转操作
j = i + 1
end = len(nums) - 1
while j < end:
nums[j], nums[end] = nums[end], nums[j]
j += 1
end -= 1
else:
# 重新寻找从右往左第一个不是降序的位置（即找到最左边的那个非降序数字）
leftmost_not_descending = -1
for p in range(n - 1, 0, -1):
if nums[p] > nums[p - 1]:
leftmost_not_descending = p - 1
break
if leftmost_not_descending!= -1:
# 在它后面的数字中找到比它大的最小数字
rightmost_greater = n - 1
while nums[rightmost_greater] <= nums[leftmost_not_descending]:
rightmost_greater -= 1
# 交换这两个数字
nums[leftmost_not_descending], nums[rightmost_greater] = nums[rightmost_greater], nums[leftmost_not_descending]
# 再将交换位置后的后面部分数组反转
start = leftmost_not_descending + 1
end = len(nums) - 1
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
return nums
————————————————————————————————————————————————
解答错误
262 / 266 个通过的测试用例
官方题解
输入
nums =
[3,2,1]
添加到测试用例
输出
[3,2,1]
预期结果
[1,2,3]
在上述修改后的代码中：
- 当没有找到相邻升序对（即
i < 0）时，我们通过一个新的循环for p in range(n - 1, 0, -1):重新寻找从右往左第一个不是降序的位置（也就是最左边的那个非降序数字），并记录其索引为leftmost_not_descending。 - 如果找到了这样的位置（
leftmost_not_descending!= -1），我们接着在它后面的数字中通过while nums[rightmost_greater] <= nums[leftmost_not_descending]: rightmost_greater -= 1找到比它大的最小数字，记录其索引为rightmost_greater。 - 然后交换这两个数字，最后再通过一个新的
while循环对交换位置后的后面部分数组进行反转操作，以得到正确的下一个排列。
这样修改后，代码应该能够正确处理各种输入情况，包括像 nums = [5, 1, 1] 这样的特殊情况，从而通过所有的测试用例。
分析一下当前代码对于输入 nums = [3, 2, 1] 输出不符合预期的情况以及如何修改代码来解决这个问题。
问题分析
对于输入 nums = [3, 2, 1]，当前代码的执行过程如下：
首先，从后向前寻找第一个相邻升序的元素对 [i, j]，在这个例子中，整个数组是严格降序排列的，所以经过 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 这个循环后，i 的值会变为 -1，表示没有找到这样的相邻升序对。
然后，由于 i < 0，代码会执行 else 分支中的内容，也就是直接对整个数组进行反转操作。但目前代码执行反转操作后输出的结果依然是 [3, 2, 1]，这是因为在反转数组的代码部分存在问题。
仔细查看反转数组的代码：
i = 0
end = len(nums) - 1
while i < end:
nums[i], nums[end] = nums[end], nums[i]
i += 1
end -= 1
这里的问题在于，当 i 和 end 相等时，循环就会停止，而对于长度为偶数的数组，这样会导致数组中间的两个元素没有进行交换，从而不能正确地将数组反转成升序排列。例如对于 [3, 2, 1]，经过上述反转代码后，实际上只交换了 3 和 1，而 2 没有参与交换，数组依然保持降序。
正确修改方案
为了正确地反转数组，我们需要修改反转数组的循环条件，确保即使数组长度为偶数，也能将所有元素正确地反转成升序排列。以下是修改后的完整代码：
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 特殊：空排列
if len(nums) == 0:
return
# 从末尾到头寻找“关键位置”, 24153中的1
# 找到后，[5,3]中找到第一个比1大的3
# 时间复杂度：O(n)，n为数组长度，主要由三个while循环决定，每个while循环最多遍历n次
# 空间复杂度：O(1)，只使用了几个额外的指针变量，不随数组长度变化
n = len(nums)
i = n - 2
# 从后向前，寻找第一个相邻升序[i, j]（后比前大）的位置
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
k = len(nums) - 1
# 在[j, end)从后往前，寻找第一个比nums[i]大的nums[k]
while nums[i] >= nums[k] && k > i:
k -= 1
# 找到k
# 交换nums[i] 与nums[k]
nums[i], nums[k] = nums[k], nums[i]
# 对交换后的 [j, end) 区间进行反转操作
j = i + 1
end = len(nums) - 1
while j < end:
nums[j], nums[end] = nums[end], nums[j]
j += 1
end -= 1
else:
# 直接反转
i = 0
end = len(nums) - 1
while i <= end:
nums[i], nums[end] = nums[end], nums[i]
i += 1
end -= 1
return nums
在上述修改后的代码中，我们将反转数组部分的循环条件 while i < end: 修改为了 while i <= end:，这样就能确保数组中的所有元素都能参与交换，从而正确地将数组反转成升序排列。经过这样的修改，对于输入 nums = [3, 2, 1]，代码应该能够输出正确的结果 [1, 2, 3]，并且有望通过所有的测试用例。
100%了
原文地址：https://blog.csdn.net/weixin_47868976/article/details/143697214
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！