31. 下一个排列

问题

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

若是不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

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

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

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

解题思绪

思绪:迭代

首先先明白题意,问题中要求【将给定数字序列重新排列成字典序中下一个更大的排列。若是不存在,则将数字重新排列称最小的排列(即升序排列)】

在这里,可能直接从文字上面来看,不太不能够明白是什么意思,那么连系例子来看,先看

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

在这里,你可以明白为,要将数字 123 变为下一个更大的数字,132。115 也同理。

而下面这个例子就是示意不存在更大的排列:

3,2,1 → 1,2,3

321 已经是最大的了,那么就将其排列为最小的排列(升序排列),获得效果 123。

实在从上面的例子中,多多少少也能够看出来,在这里实在是从后面最先找,当找到相邻升序的两个数字,在这里将它们举行交流,这样就能够获得更大的排列。

实在这里另有一部门的内容,在问题中是对照难看出来的,问题中【下一个】这个观点,实在要找到的是转变前后的排列,增添的幅度尽可能小。好比,下面的例子:

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

第一个示例,凭据上面考察所得,即是将 4 和 5 举行替换,获得更大的排列,12354。

后面的示例中 12354,获得排列的效果 12435。在这里,交流的是 3 和 4,这里实在交流的数字是尽可能小的大数和前面的小数,以是并不是 3 和 5 举行交流,而交流后的所有数还需要重置升序。所得出的效果是 12435,而不是 12453。

这就是关于题意的简朴剖析,下面看若何实现算法:

  • 首先需要明确的是从后面往前查找第一个相邻升序的两个元素所在的位置(i,j),知足 A[i] < A[j]。而且,从位置 j 往后的元素是降序的。
  • 在 j 往后的元素中,同样是从后往前找,找到第一个知足 A[i] < A[k] 的元素,将其两者举行交流。
  • 前面说了, 从 j 往后一定是降序的,那么交流以后一定也是降序的(由于找到 A[k] 是第一个比 A[i] 大的数字,由于是从后往前找,k所在位置左边的数字势必比当前 i 所在位置的数字大,而右边的数字也就比其小),这个时刻,要将这部门降序,逆转为升序,这样才气保证排列前后尽可能小的增幅。
  • 思量特殊的情形,也就是整个排列是降序,即是最大的的排列时,执行上面所说逆转为升序即可。

详细的代码实现如下。

代码实现

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) < 2:
            return

        n = len(nums)

        # 从数组右往前举行遍历,查找相邻升序元素
        i = n - 2
        j = n - 1
        while i > 0 and nums[i] >= nums[j]:
            i -= 1
            j -= 1
        # 这里有一种情形,就是循环竣事后,i 为 0 且索引 0 位置的数是最大的情形
        # 那这里就示意排列就是最大的排列,将其逆转升序
        if i == 0 and nums[i]==max(nums):
            nums.reverse()
        else:
            # 当找到相邻的升序元素时
            # 再次从后往前找到一个比 nums[i] 大但相比其他元素尽可能小的数
            k = n - 1
            while nums[i] >= nums[k]:
                k -= 1
            # 交流两个元素
            nums[i], nums[k] = nums[k], nums[i]

            # 现在 j 到后面的元素是降序的,这里要将其升序
            length = n - j + 1
            for x in range(length // 2):
                nums[j+x], nums[n-1-x] = nums[n-1-x], nums[j+x]

实现效果

以上就是关于《31. 下一个排列》问题的剖析及详细实现算法的主要内容。

迎接关注微信民众号《书所集录》

,

Sunbet

Sunbet www.895612.com www.sunbet.us是sunbet的唯一平台。Sunbet开放Sunbet会员开户网址、Sunbet代理开户、Sunbet手机版下载、Sunbet电脑客户端下载等业务。

Allbet Gaming声明:该文看法仅代表作者自己,与阳光在线无关。转载请注明:潍坊百姓网:LeetCode 31. 下一个排列 | Python
发布评论

分享到:

日照大众网:API 网关 Kong
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。