Next Permutation

Question

Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Example

For [1,3,2,3], the next permutation is [1,3,3,2]

For [4,3,2,1], the next permutation is [1,2,3,4]

Note The list may contains duplicate integers.

Thoughts

refer 这种看起来比较模糊的题目，可以先写出几个例子来找到规律和感觉

7 2 5 2(c) 3 1
7 2 5 3 1(c) 2 
7 2(c) 5 3 2 1
7 3 1 2 2 5

(c) means the position that needs most significant position that needs change

可以找到感觉，发现找到next permutation的规律是有三步

1. 从右往左找到第一个非递增的数 s[i] < s[i+1]
   • 如果找到头依然没有，说明已经最大，next permutation就是reverse得到最小的数
2. 从i的右边，找到比s[i]大的最小值，因为右边是从右往左递增的，所以找法就是s[j] > s[i] >= s[1], swap s[i] 和s[j]
3. 现在要得到右边最小的数，就将i右边的数字递增排序，注意python的语法s[i+1:lengh] = s[length-1:i:-1]

注意点

• 已经是最大的情况
• 找到大的最小值和reverse时候的边界处理

Solution

class Solution:
    # @param num :  a list of integer
    # @return : a list of integer
    def nextPermutation(self, num):
        # write your code here 
        if not num:
            return None
        length = len(num)
        i = length - 2
        while i >= 0:
            if num[i] < num[i+1]:
                break
            i -= 1
        if i == -1:
            num.reverse()
            return num
        for j in range(i+1, length):
            if j == length - 1:
                break
            if num[j] > num[i] and num[i] >= num[j+1]:
                break
        tmp = num[i]
        num[i] = num[j]
        num[j] = tmp
        num[i+1:length] = num[length-1:i:-1]

        return num