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, do not allocate 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

解题方法

• 从右往左，找出第一个递减的数，记它的index为i
• 在i的右边，找到比它value大的最小值，index记为j，将i和j swap
• 将[i+1:]的array reverse,变成Increasing sequence

Solution

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return
        length = len(nums)
        if length == 1:
            return
        #from right to left, find first descending number
        i = length - 2
        while i >= 0:
            if nums[i] < nums[i+1]:
                break
            i -= 1
        if i == -1:
            #no descending number, it's already largest
            nums.reverse()
            return 

        j = i + 1
        while j < length - 1:
            if nums[j] > nums[i] and nums[j+1] <= nums[i]:
                break
            j += 1
        #swap i and j
        tmp = nums[j]
        nums[j] = nums[i]
        nums[i] = tmp
        nums[i+1:length] = nums[length-1:i:-1] #python的这个方法很好用

Reference