31. Next Permutation

下一排列

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].
  给定一个整数数组的一个排列，将其所有成员以序列或线性顺序排列。

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
只能在原地修改，不能使用额外的数组空间。即算法的空间复杂度O(1)。

Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:
Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

思考

首先不太理解什么叫做下一个排列。从题目来看是按照字典顺序排列。不太理解什么是字典排序，就从网上查询了一下。字典排序参考链接
字典排序感觉描述起来不太好理解。就好比在字典排序里面2比12大的原因是因为第一位数字比他大。按位比较，当有一位比他大的时候就比他大。

根据参考网站里面别人提供的算法，总共有四步。
第一步：从右往左找出第一个左边小于右边的数字，记为a
第二步：从右往左找出第一个比a大的数字，记为b
第三步：交换a和b的位置。
第四步：将a所在位置后面的位置按照从小到大进行排序。

但是既然算法这么明确，那这题好像就没有什么难度了。我们先实现看一下。

class Solution:
    def shell_sort(self, l, a):
        for i in range(a, len(l)):
            for j in range(i, len(l)):
                if l[i]>l[j]:
                    tmp = l[i]
                    l[i] = l[j]
                    l[j] = tmp
            
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l = len(nums)
        a = -1
        b = -1
        for i in range(l-1,-1,-1):
            if nums[i]>nums[i-1]:
                a = i-1
                break
        for i in range(l-1,a-1,-1):
            if nums[i]>nums[a]:
                b = i
                break
        if a==-1 and b==-1:
            self.shell_sort(nums, 0)
        else:
            tmp = nums[a]
            nums[a] = nums[b]
            nums[b] = tmp
            self.shell_sort(nums, a+1)

空间是节省下来了，但是时间的消耗简直不忍直视

image.png

答案解析

暴力破解

找出所有的关于当前列表的字典排列，然后找到和比当前大的下一个排列。
但是这样很明显会超时。。

两遍扫描

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1
            while j >= 0 and nums[i] >= nums[j]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

这个从中国站的力扣上的答案来看，和我自己从参考资料里面看到的算法是一样的。但是实现起来比我的更加整洁。由于算法已知，a右边的排序已经是降序的了，所以可以简单的使用双指针反转区间的方式进行升序排序。比我的冒泡效率会高一些。

总结

每做一步要知道这一步之后的数据结构会变成什么样。
题目和答案来自美国站的leetcode和中国站的力扣。仅供参考