31. Next Permutation【下一个排列】

﹏ヽ暗。殇╰゛Y 2022-04-23 06:24 153阅读 0赞

Implement **next permutation**, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be **[in-place][]** and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

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

--------------------

题目大意：

找到序列的下一个比它大的排列，如果该序列为最大序列则返回最小的排列。

--------------------

解题思路：

如果该序列为最大序列，从后往前看，该序列为非递减序列，非递减即存在111,222,333等排列。所以从后向前，找到第一个不满足非递减序列的位置nums\[k\]，即nums\[k\] < nums\[i\]。

不为最大序列时，如何求得下一个排列？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjAwMTM3_size_16_color_FFFFFF_t_70][]

--------------------

class Solution:
        def nextPermutation(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            len_nums = len(nums)
            idx = -1
            
            for i in range(len_nums - 2, -1, -1):
                if nums[i] < nums[i + 1]:
                    idx = i
                    break
            if idx == -1:
                reverse(nums, idx)
            else:
                for j in range(len_nums - 1, idx, -1):
                    if nums[j] > nums[idx]:
                        nums[j], nums[idx] = nums[idx], nums[j]
                        break
                reverse(nums, idx)
        
    def reverse(nums, i):
        l = i + 1
        r = len(nums) - 1 
            
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

[in-place]: http://en.wikipedia.org/wiki/In-place_algorithm
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjAwMTM3_size_16_color_FFFFFF_t_70]: /images/20220323/d1e9964298f948c893b2300e5c78c9e8.png