前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Leetcode][python]Next Permutation/下一个排列

[Leetcode][python]Next Permutation/下一个排列

作者头像
蛮三刀酱
发布2019-03-26 17:02:33
7270
发布2019-03-26 17:02:33
举报
文章被收录于专栏:蛮三刀的后端开发专栏

版权声明:本文为博主原创文章,转载请注明原文地址链接。 https://cloud.tencent.com/developer/article/1407142

题目大意

寻找一组数排序的下一个序列

例如:1,2,3,下一个就是1,3,2

解题思路

官方思路(与下方相同):https://leetcode-cn.com/problems/next-permutation/solution/

http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html

图中文字翻译:

  1. 从右向左,找到第一个违反生序的,也就是图中的6,叫他‘partitionnumber’。
  2. 从右向左,找到第一个比刚才那个数大的数,叫他‘changenumber’。
  3. 交换着两个数,然后把在partitionnumber右边的数顺序反过来。

代码

代码语言:javascript
复制
class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        partition = -1
        for i in range(len(nums)-2, -1, -1):  # 从倒数第二个数开始遍历到第0个数 
            if nums[i] < nums[i+1]:  # 从后向前找到第一个升序对,并让partition等于升序对中较小的
                partition = i
                break
        if partition == -1:
            # 没找到升序对 e.g. 54321 --> 12345
            nums.reverse()
        else:
            for i in range(len(nums)-1, partition, -1):
                # 交换partition和升序对后面比partition更大的数 如14532 -> 15432
                if nums[i] > nums[partition]:
                    nums[i], nums[partition] = nums[partition], nums[i]
                    break
        # 将partition后面的数字逆向排序。由于找到的partition是从后向前的第一个升序对,所以可以放心partition后面一定都是降序的
        # 所以逆向排序后可以得到一个新的刚好大于之前permutation的next permutation
        # 比如此时14532已经变为15432,则再将5(此时partition已经是5了)后面的432逆序排列得到234.则最终的数字变为15234
        nums[partition+1:len(nums)] = nums[partition+1:len(nums)][::-1]  # 切片

总结

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年09月07日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目大意
  • 解题思路
  • 代码
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档