美文网首页
31. 下一个排列

31. 下一个排列

作者: oneoverzero | 来源:发表于2020-02-04 11:13 被阅读0次

题目描述:

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

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

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

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

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

代码:

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        is_possible = False
        
        # step 1: find the first nums[i] < nums[ii] from the tail
        for i in range(len(nums)-1, 0, -1):
            if nums[i-1] < nums[i]:
                i, ii = i-1, i
                is_possible = True
                break
        
        # step 2: find the first nums[j] > nums[i] from the tail and swap nums[i], nums[j]
        if is_possible:
            for j in range(len(nums)-1, -1, -1):
                if nums[j] > nums[i]:
                    nums[i], nums[j] = nums[j], nums[i]
                    # step 3: reverse all the elements starting from ii
                    nums[ii:] = nums[ii:][::-1]
                    break
        else:
            nums[:] = nums[::-1]

什么是下一个排列以及本题的思路分析:

核心思想是:

  • step 1:首先从最尾端开始往前寻找两个相邻元素,令第一元素为 i ,第二个元素为 ii ,且满足 nums[i] < nums[ii]
  • step 2:找到这样一组相邻元素后,再从最尾端开始往前检验,找出第一个大于 i 的元素,令为 j ,将 nums[i]nums[j] 对调;
  • step 3:再将 nums[ii:] 反转(reverse)。

曾出错过的地方:

  • 题目中明确说明不能返回任何东西,所以最开始写代码时,发现在VScode中能够通过,但是在LeetCode中总是报错,而且在LeetCode中的输出和在VScode中的输出不一致。后来发现是自己在代码中写了 return nums 语句,从而导致出错;
  • range左闭右开 的,在上述代码中用到了两处 range ,第一处是 range(len(nums)-1, 0, -1) ,这里右边只能取到 1,是无法取到 0 的(第二处的 range(len(nums)-1, -1, -1) 只能取到 0 而无法取到 -1),这一点在写代码时必须非常明确,否则非常容易出错。
  • 最后的 else 语句不能写成 nums = nums[::-1]

相关文章

  • LeetCode-31-下一个排列

    LeetCode-31-下一个排列 31. 下一个排列[https://leetcode-cn.com/probl...

  • LeetCode 31. 下一个排列 | Python

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

  • 31. 下一个排列

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

  • 全排列问题偷鸡做法

    全排列问题偷鸡摸狗做法用强大的(猥琐的)next_permutation 31. 下一个排列 46. 全排列 47...

  • 每日一题20201118(31. 下一个排列)

    31. 下一个排列[https://leetcode-cn.com/problems/next-permutati...

  • LeetCode每日一题: 31. 下一个排列

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

  • 【LeetCode】排列问题

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

  • 31. 下一个排列

    31. 下一个排列 题目链接:https://leetcode-cn.com/problems/next-perm...

  • LeetCode-31 下一个排列

    题目:31. 下一个排列 难度:中等 分类:数组 解决方案:数组遍历 今天我们学习第31题下一个排列,这是一个中等...

  • ARTS打卡第六周

    ARTS打卡第六周 Algorithm:每周至少做一个 leetcode 的算法题 31. 下一个排列 代码: 官...

网友评论

      本文标题:31. 下一个排列

      本文链接:https://www.haomeiwen.com/subject/onfrxhtx.html