【31. Next Permutation - Python】IDE通过，leetcode不通过

以下是小弟的solution:

# 31. 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

class Solution:
    def nextPermutation(self, nums) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) <= 1:
            return nums

        for i in list(range(len(nums)-1, 0, -1)):
            if nums <= nums[i-1]:
                pass
            else:
                k = self.switch_pos(i-1, len(nums)-1, nums)
                nums[i-1], nums[k] = nums[k], nums[i-1]
                a = nums[i:]
                a.sort()
                return nums[:i] + a

        nums.sort()
        return nums

    def switch_pos(self, start, end, nums):
        curr = end
        while curr >= start:
            if nums[curr] > nums[start]:
                return curr
            else:
                curr -= 1

if __name__ == '__main__':
    x = Solution()
    nums = [1, 3, 2]
    print(x.nextPermutation(nums))

Test case: nums = [1, 3, 2]

在本地output是[3, 1, 2]，正确。但Leetcode提交后显示
Your input
[1, 3, 2]
Output
[2,3,1]
Expected
[2,1,3]

请问是咋回事？

没仔细看算法是否正确 但是for循环中的a没有modify nums in place

yayafuture 发表于 2019-8-2 14:27
没仔细看算法是否正确 但是for循环中的a没有modify nums in place

是的, 没有modify nums in place。但我本意就不是modify in place。

a = nums[i:]
a.sort()
return nums[:i] + a

我只是把nums的一部分sort，然后再和nums的前半部分合并起来。

mmxmw 发表于 2019/08/02 15:01:57


是的, 没有modify nums in place。但我本意就不是modify in place。

a = nums[i:]
a.sort()
return nums[:i] + a
...

那lc肯定不过啊……lc要求in place的

上面楼说的in-place问题是对的，你把

1. return nums[:i] + a

复制代码

改成下面两行

1. nums[:] = nums[:i] + a
   
2. return

复制代码

就可以通过了

至于为什么IDE可以通过而LeetCode不通过，是因为你的本地代码使用了nextPermutation的返回值：

1. print(x.nextPermutation(nums))

复制代码

而LeetCode测试这道题的代码应该是类似于这样：

1. x.nextPermutation(nums)
   
2. print(nums)

复制代码