LeetCode 刷题记录: 31. Next Permutation [Python]

原题

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

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

思路

指针i从后往前找到第一个前面比后面小的数nums[i-1]，此时i:end均为从大到小排序。
指针j从后往前找到第一个比nums[i-1]大的数nums[j]。此时nums[j]为i:end中的最小数。
交换nums[i-1]与nums[j]，此时i:end依然为从大到小排序。
将i:end倒序，此时变成从小到大排序。完成。

代码

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        if n<2: return
        i=j=n-1
        while i>0 and nums[i-1]>=nums[i]:
            i-=1
        if i>0:
            while nums[j]<=nums[i-1]:
                j-=1
            nums[i-1],nums[j]=nums[j],nums[i-1]
        nums[i:]=reversed(nums[i:])

# LeetCode, Premutation, Tricky

支付宝

微信

Paypal Buy me a coffee

LeetCode 刷题记录: 31. Next Permutation [Python]

原题

思路

代码

喜欢这篇文章？打赏一下作者吧

评论

分类

标签

最新文章

归档

最新文章

归档

Your browser is out-of-date!