###### tags: `Leetcode` `medium` `array` `python` `Top 100 Liked Questions`

# 31. Next Permutation

## [題目來源:] https://leetcode.com/problems/next-permutation/

## 題目:
A **permutation** of an array of integers is an arrangement of its members into a sequence or linear order.

* For example, for ```arr = [1,2,3]```, the following are all the permutations of ```arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]```.

The next **permutation** of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the **next permutation** of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

* For example, the next permutation of arr = [1,2,3] is [1,3,2].
* Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
* While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers ```nums```, find the next permutation of ```nums```.

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]

## 解題想法:
* 找比現在數值再大的下個值
* ex: 1 2 3 -> 下個為 1 3 2 -> 下個為 2 1 3......
* 以case1為例: ex: 5 3 4 2 1
* **step1** 從**尾**進行遍歷 找到第一個降序的數字(數字3) 因為4->3為降序
* **step2** 從**尾**進行遍歷 找到第一個比目前數字大的值(數字4)
* **step3** swap 3、4 -> 5 4 3 2 1
* **step4** 雖然比nums大，但不是下一個大的，須對後面的 321進行排序變成123
* 最終5 4 1 2 3即為解
* case2: 5 4 3 2 1 不存在升序
* 反序 1 2 3 4 5 即可

## Python:

class Solution:
    def nextPermutation(self, nums):
        n = len(nums)
        #從數組的倒數第二位進行遍歷
        #因為要比較n與n+1大小判斷降序
        i = n-2
        while i>=0:
            #若為安全的升序
            if nums[i]>=nums[i+1]:
                i-=1
            #為降序
            else:
                #從尾找比該nums[i]值大的
                for j in range(n-1,i,-1):
                    if nums[j]>nums[i]:
                        nums[i],nums[j] = nums[j],nums[i]
                        #將i+1到尾從新排好
                        nums[i+1:] = sorted(nums[i+1:])
                        return
        nums.reverse() #若原本就是由大到小

if __name__ == '__main__':
    result = Solution()
    nums = [3,2,1]
    result.nextPermutation(nums)
    print(nums)