[LeetCode] 31. Next Permutation

轉自LeetCode

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

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

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

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

<Solution>

這題看到 lexicographical order，然後要求下一個排列是什麼，並且要 in-place

直覺就是用 next_permutation

code 如下

那如果不用 next_permutation呢？

就要用個演算法來檢查 (參考資料1，參考資料2)

因為是要求 lexicographical 的下一個排序，所以在字典順序上的改變愈少愈好

用例子說明

0  1  2  5  3  3  0 的下一個排序是 0  1  3  0  2  3  5

以下是分析

• 從後往前找到第一個不是升冪到數字 pivot_1

     0  1  2  5  3  3  0

• 再從後往前找到第一個大於 pivot_1 的數字 pivot_2

     0  1  2  5  3  3  0

• swap pivot_1 和 pivot_2

     0  1  3  5  3  2  0

• 然後將 pivot_1 之後的數字做 reverse，把它變成 increasing order。因為 increasing order 在 lexicographical order 來說是小於 decreasing order 的

    0  1  3  0  2  3  5

這樣就找到 next permutation 了

code 如下

c++

kotlin