LeetCode Next Permutation

LeetCode解題之Next Permutation

原題

找出一個數組按字典序排列的後一種排列。

注意點：

例子：

輸入: [1,2,3]
輸出: [1,3,2]

輸入: [3,2,1]
輸出: [1,2,3]

解題思路

通過一個例子來說明，原數組為[1,7,3,4,1]。我們想要找到比173421大一點的數，那就要優先考慮將後面的數字變換順序，而421從後往前是升序的（也就是這三個數字能組成的最大的數），變換了反而會變小，所以要先找到降序的點。可以看出3是第一個降序的點，要想整個數變大，3就要變大，從後往前找到第一個比3大的數4，將3和4交換位置得到174321，既然原來3所在位置的數字變大了，那整個數肯定變大了，而它之後的數是最大的（從後往前是升序的），應轉換成最小的，直接翻轉。

AC源碼

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

        targetIndex = 0
        changeIndex = 0
        for i in range(length - 1, 0, -1):
            if nums[i] > nums[i - 1]:
                targetIndex = i - 1
                break
        for i in range(length - 1, -1, -1):
            if nums[i] > nums[targetIndex]:
                changeIndex = i
                break
        nums[targetIndex], nums[changeIndex] = nums[changeIndex], nums[targetIndex]
        if targetIndex == changeIndex == 0:
            nums.reverse()
        else:
            nums[targetIndex + 1:] = reversed(nums[targetIndex + 1:])

歡迎查看我的Github來獲得相關源碼。