Source: Next Permutation

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

If such arrangement is not possible, it must be rearranged as the lowest possible order ie, sorted in an ascending order.

The replacement must be in-place, do not allocate extra memory.

Examples:

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

20, 50, 113 → 20, 113, 50

Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

Warning : DO NOT USE LIBRARY FUNCTION FOR NEXT PERMUTATION.

Use of Library functions will disqualify your submission retroactively and will give you penalty points.

解題：
  1. 如果是在實際的面試場合，應該要先問或測試清楚題目裡面的排列跟次一排列到底是採用什麼邏輯，題目給的資訊其實蠻籠統的……
    以[20, 50, 113]為例：

    1. [20, 50, 113]
    2. [20, 113, 50]
    3. [50, 20, 113]
    4. [50, 113, 20]
    5. [113, 20, 50]
    6. [113, 50, 20]
    7. Back to (a.)
  2. 因此迴圈先測試是否完全符合降冪（情況f.），如是則回傳(a.)，如否則記住索引值 i 的位置並跳出迴圈進入下個階段；
  3. 跳出後一樣從陣列尾往前找，找到第一個符合條件A[j] > A[i]的索引值 j ，並對調A[j] 及 A[i]；
  4. 因在索引值 i 以後都呈現降冪排列，故完成對調後再將 i+1 至 n-1間之數值全數調換即可。

Code:

class Solution:
    # @param A : list of integers
    # @return the same list of integer after modification
    def nextPermutation(self, A):
        N = len(A)
        if N == 1: return A
        else:
            i = N-2
            while i >= 0 and A[i] >= A[i+1]: i -= 1
            if i == -1: return A[::-1]
            else:
                for j in range(N-1, i, -1):
                    if A[j] > A[i]: break
                A[i], A[j] = A[j], A[i]
                a, b = i+1, N-1
                while a < b:
                    A[a], A[b] = A[b], A[a]
                    a += 1
                    b -= 1
        return A

GitHub: GitHub

發表留言