題目鏈接
難度：中等 ??????類型： 數(shù)組

實現(xiàn)獲取下一個排列的函數(shù)，算法需要將給定數(shù)字序列重新排列成字典序中下一個更大的排列。

如果不存在下一個更大的排列，則將數(shù)字重新排列成最小的排列（即升序排列）。

必須原地修改，只允許使用額外常數(shù)空間。

示例

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

解題思路

1376542 的下一個排列為 1423567
可以看出，需要改變的子數(shù)組的起始數(shù)為 從后往前第一個nums[i]>nums[i-1]的數(shù)k，即3
要把起始數(shù)k替換為從后往前第一個大于k的數(shù)，即4，交換兩數(shù)變?yōu)?476532
翻轉(zhuǎn)i之后的一半數(shù)組

有一種特殊情況：倒序遍歷到0都沒有碰到nums[i]>nums[i-1]的情況，直接翻轉(zhuǎn)整個數(shù)組

代碼實現(xiàn)

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = j = n-1
        while i > 0 and nums[i-1] >= nums[i]:
            i -= 1  
        k = i - 1    # find the last "ascending" position
        if k>=0:
            while nums[j] <= nums[k]:
                j -= 1
            nums[k], nums[j] = nums[j], nums[k]  
        l, r = k+1, n-1  # reverse the second part
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l +=1 ; r -= 1

本文鏈接：http://www.itdecent.cn/p/735a067d9a1e