• 分类：Array

• 考察知识点：Array(数组遍历) 数学

• 最优解时间复杂度：O(2n+n^2)

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.

Example:

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

代码：

我的解法:

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

        pointer=len(nums)-1
        largest=nums[pointer]

        for i in range(len(nums)-2,-1,-1):
            if nums[i]>=largest:
                largest=nums[i]
                pointer=i
            else:
                break

        if pointer!=0:
            for i in range(len(nums)-1,pointer-1,-1):
                if nums[i]>nums[pointer-1]:
                    temp=nums[pointer-1]
                    nums[pointer-1]=nums[i]
                    nums[i]=temp
                    break
            nums=self.bubbleSort(nums, pointer, len(nums))
            # return nums
        else:
            nums=self.bubbleSort(nums,0,len(nums))
            # return nums

    #冒泡排序法
    def bubbleSort(self, nums, start, end):
        # inplace method
        n=0
        for i in range(start,end):
            for j in range(start,end-n-1):
                if nums[j+1]<nums[j]:
                    temp=nums[j]
                    nums[j]=nums[j+1]
                    nums[j+1]=temp
            n+=1
        return nums

取巧的Python解法

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

        pointer=len(nums)-1

        for i in range(len(nums)-2,-1,-1):
            if nums[i]>=nums[i+1]:
                pointer=i
            else:
                break

        if pointer!=0:
            for i in range(len(nums)-1,pointer-1,-1):
                if nums[i]>nums[pointer-1]:
                    nums[pointer-1],nums[i]=nums[i],nums[pointer-1]
                    break
            nums[pointer:]=nums[pointer:][::-1]
            # return nums
        else:
            nums[:]=nums[::-1]
            # return nums

讨论：

1.我写的方法就是最正常的方法，没有使用任何取巧的方法
2.我写的第一个方法值得一提的是，冒泡排序法里面的那个括号里记得-1
3.方法2是一个用Python里面一些东西显得比较取巧的方法，速度贼快！
4.但记得是nums[:],不能写nums,如果是写nums就是重新找一个地方赋值，不是原来的了
5.另外就是Permutation的定义是全数列，就是全部排列组合，Next Permutation就是指排列组合的下一个

常规方法

取巧方法