Leetcode: Next Permutation

這道題的算法第一次可能有點難想，但是做過一次後就知道了

Shi Li Analysis（會好了解很多）:

Starting from the last position, the first time we find that num[i]<num[i+1], we stop. The position i is the position that will be increased. We need to find out the next large num in num[i+1...len-1] and change num[i] to that number. Suppose it is num[j], then num[i]=num[j]. For the rest part to the array, we arrange them in an increasing order of num[i]...num[len-1] except num[j]. 

we actually can observe that the part num[i+1]...num[len-1] is actually reversely ordered already. Therefore, all we need to do is find out num[j], and reverse the part num[i]...num[len-1]. The complexity is decreased to O(n).

用一個例子來說明，比如排列是(2,3,6,5,4,1)，求下一個排列的基本步驟是這樣：

1) 先從後往前找到第一個不是依次增長的數，記錄下位置p。比如例子中的3，對應的位置是1;

2) 接下來分兩種情況：

    (1) 如果上面的數字都是依次增長的，那麼說明這是最後一個排列，下一個就是第一個，其實把所有數字反轉過來即可(比如(6,5,4,3,2,1)下一個是(1,2,3,4,5,6));

    (2) 否則，如果p存在，從p開始往後找，找到下一個數就比p對應的數小的數字，然後兩個調換位置，比如例子中的4。調換位置後得到(2,4,6,5,3,1)。最後把p之後的所有數字倒序，比如例子中得到(2,4,1,3,5,6), 這個即是要求的下一個排列。

以上方法中，最壞情況需要掃描數組三次，是以時間複雜度是O(3*n)=O(n)，空間複雜度是O(1)。

至于一些細節5行第二個不等号是>=而不是 >,  第10行第二個不等号是>而不是>=, 推導一下 {2,3,5,5,4,3}這個例子