動機

這是經典演算法，基本上沒有寫過就要在面試時寫出來，應該十分困難

Problem

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

 

Example 1:

Input: nums = [1,2,3]Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]Output: [1,5,1]

Example 4:

Input: nums = [1]Output: [1]

 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

原理

1 2 3 最後要變成 3 2 1 觀察3 2 1的大小，都是 前一個大於等於下一個 (字典序最大)

那麼如果再加一個數字像0 3 2 1就會破壞這個規則， 所以要重新往 前一個大於等於下一個 這個條件靠近。

因為我們要的是下一個字典序的排列(與現在排列差異最小)， 所以下一個排列的第一個要從現有的部分挑一個最小的來換，讓第一位差異最小， 我們可以從中挑一個大於那個數字的最小數來交換

延續上面例子會變成1 3 2 0

接著是原本的範圍如何讓他的字典序最小? reverse!!

所以下一個排序是1 0 2 3

def findStartOfRevOrder(arr):
    i = len(arr)-1 # start from the last index
    while i > 0 and arr[i-1] >= arr[i]:
        i -= 1
    return i if i > 0 else -1
def reverse_in_place(alist,left,right):
    #condition for termination
    while left<right:

       #swapping
       temp = alist[left]
       alist[left] = alist[right]
       alist[right] = temp

       #updating pointers
       left += 1
       right -= 1
class Solution:
    def nextPermutation(self, arr: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = findStartOfRevOrder(arr)-1
        j = len(arr)-1
        if i >= 0:
            while j >= 0 and arr[i] >= arr[j]: # keep the small ones in last
                j -= 1
            if j >= 0:
                # swap
                arr[i], arr[j] = [arr[j],arr[i]]
                #arr[i+1:] = arr[i+1:][::-1] # keep big digit as the last
                reverse_in_place(arr,i+1,len(arr)-1)
        else:
            reverse_in_place(arr,0,len(arr)-1)

556

把數字當成排列

def findStartOfRevOrder(arr):
    i = len(arr)-1 # start from the last index
    while i > 0 and arr[i-1] >= arr[i]:
        i -= 1
    return i if i > 0 else -1
def f(arr):
    i = findStartOfRevOrder(arr)-1
    if i >= 0:
        j = len(arr)-1
        while j >= 0 and arr[i] >= arr[j]: # keep the small ones in last
            j -= 1
        if j >= 0:
            # swap
            arr[i], arr[j] = [arr[j],arr[i]]
            arr[i+1:] = arr[i+1:][::-1] # keep big digit as the last
            i = findStartOfRevOrder(arr)-1
            return arr
    else:
        return False
class Solution:
    def nextGreaterElement(self, n: int) -> int:
        arr = [int(c) for c in str(n)]
        ret = f(arr)
        if ret:
            ret = [str(n) for n in ret]
            ret = int(''.join(ret))
            if ret >= 2147483647:
                ret = -1
        else:
            ret = -1
        return ret