• 分類：Array

• 考察知識(shí)點(diǎn)：Array(數(shù)組遍歷) 數(shù)學(xué)

• 最優(yōu)解時(shí)間復(fù)雜度：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.我寫的第一個(gè)方法值得一提的是，冒泡排序法里面的那個(gè)括號(hào)里記得-1
3.方法2是一個(gè)用Python里面一些東西顯得比較取巧的方法，速度賊快！
4.但記得是nums[:],不能寫nums,如果是寫nums就是重新找一個(gè)地方賦值，不是原來的了
5.另外就是Permutation的定義是全數(shù)列，就是全部排列組合，Next Permutation就是指排列組合的下一個(gè)

常規(guī)方法

取巧方法