31. 下一个排列 [medium]

https://leetcode-cn.com/problems/next-permutation/

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

通过次数75,845 | 提交次数221,799

First Try

2020-07-24

这种题目是目前对我比较棘手的类型，一点小数组然后就搞个莫名其妙的组合问题出来。

要找到下一个比当前数字更大的元素，为了影响最小，显然需要从最末尾开始换起。但是观察也只能观察出有限的规律，一开始打算用从最后端开始进行换位，类似于倒序的冒泡排序，写着写着测试案例就挂掉了。

看题解才知道按照需要按照倒序和正序两个基础概念来。对于一个数组，当其按照正序排列时，这是最小值；当其按照倒序排列时，这是最大值。

为了影响最小，显然需要从最末尾开始换起。但是如果后n位都是倒序，则不管在后n位怎么换，都只能变得更小，只能考虑倒数第n+1位。如果倒数n+1位小于倒数第n位，则n+1位必须被更换，问题变成了换哪一个？

把倒数第n位和第n+1位互换，显然可以实现变大，但并不是下一个更大。需要找的是在倒序数组里，比倒数第n+1位元素稍微大一点的数字进行交换，这是最合适倒数第n+1位元素的替换值。但问题并不是到这里就终止，bug也往往发生在这里。

交换完之后，还需要考虑倒数n+1位后面的数组是否已经是最小，需要将其变成正序排列才行。由于之前已经是倒序排列，因此进行reverse就行了。

另外如果整个数组本来就是倒序，那么进行reverse变成正序也搞定。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def partial_reversed(nums, start_idx):
            end_idx = len(nums) - 1
            while end_idx > start_idx:
                nums[start_idx], nums[end_idx] = nums[end_idx], nums[start_idx]
                end_idx -= 1
                start_idx += 1

        n = len(nums)
        swap_idx = n - 2 
        # 选择在降序序列的拓展过程中，第一个非降序的。 数字组合中降序排列是最大的。
        while swap_idx >= 0 and nums[swap_idx] >= nums[swap_idx + 1]:  # >= 而非> 
            swap_idx -= 1
        
        # 全组数字为降序排列，直接逆序完事
        if swap_idx == -1:
            partial_reversed(nums, 0)
            return 

        pick_idx = n - 1 
        while nums[pick_idx] <= nums[swap_idx]:
            pick_idx -= 1
        nums[pick_idx], nums[swap_idx] = nums[swap_idx], nums[pick_idx]
        # 这才是最关键的部分。。。
        # 交换之后，后面的元素部分需要进行升序排序，毕竟升序排序是最小的。 
        partial_reversed(nums, swap_idx + 1)
        

执行用时：52 ms, 在所有 Python3 提交中击败了12.40%的用户
内存消耗：13.6 MB, 在所有 Python3 提交中击败了8.33%的用户

failed try one

没考虑到在第一次交换之后，需要把交换后面的数组变成升序排列，其实就是没有观察到完整的规律。只是针对[1, 3, 3]这个测试案例进行了优化，以为是重复数字的问题。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 如果为递减数列，只能逆转。第一个不是逆转数列的元素，可以跟后面刚好比它大的元素进行替换。
        # 如果倒数第一个元素比倒数第二个元素小，直接替换就是了，这算是base condition极端情况。
        # [1, 3, 3]还真是麻烦，但好像没看到题解有考虑这种情况？
        # [1, 3, 2] 输出为[2, 1, 3] 而不是[2, 3, 1]
        n = len(nums)
        back_idx = n - 2 
        while back_idx >= 0:
            # 递减数列，一路往前找就行
            if nums[back_idx] >= nums[back_idx + 1]:  # 比下一个元素大，因此是递减
                back_idx -= 1
            else:
                break 
        if back_idx == -1:
            for i in range(n // 2):
                nums[i], nums[n - 1 - i] = nums[n - 1 - i], nums[i]
            return 
        last_idx = n - 1 
        while True: 
            # 总归会找到一个比last idx大的元素，大不了是back_idx + 1
            if nums[back_idx] < nums[last_idx]:
                break 
            last_idx -= 1 
        # 为了避免重复数据额外处理，比如[1, 3, 3]的下一个是[3, 1, 3]而不是[3, 3, 1]
        while nums[last_idx] == nums[last_idx - 1]:
            last_idx -= 1
        nums[back_idx], nums[last_idx] = nums[last_idx], nums[back_idx]
        

failed try 2

尝试使用逆序冒泡排序，先交换最后一个元素，然后最后第二个元素之类，但没有观察到完整的规律，导致失败。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 这种题都是毫无思路。。。
        # 遇到[1, 3, 3]就挂掉了，按照代码是[3, 3, 1],其实应该是[3, 1, 3]
        n  = len(nums)
        for i in range(n - 1, -1, -1):
            for j in range(i - 1, -1, -1):
                if nums[i] > nums[j]:
                    nums[i], nums[j] = nums[j], nums[i]
                    return 
        # 这个写法没法在内存中进行修改
        # nums = list(reversed(nums))
        for i in range(n//2):
            nums[i], nums[n - 1 - i] = nums[n - 1 - i], nums[i]

31. 下一个排列 [medium]​

First Try​

31. 下一个排列 [medium]

First Try