LeetCode 31. Next Permutation [Medium] [C++] 解題筆記

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 and use only constant extra memory.

EX:

        1,2,3 → 1,3,2

    3,2,1 → 1,2,3

    1,1,5 → 1,5,1

想法:

        這題要我們找到數列按照字典順序的下一個排序，我們可以把這個數列看成是一個 tree 的結構，而我們要找的就是 lca (lowest common ancestor) 最小共同祖先，例如 1,2,3 的 lca 就是 1 ，1, 2, 5, 4, 3 的 lca 是 1，可以發現 lca 的下一個 子樹就是下一個排列方式，因此這題可以照以下方式求解:

 Step 1. find lowest common ancestor

 Step 2. find next subroot according to this lca

 Step 3. reverse of remaining element is the first permutation of this subroot

首先先找到 lca 之後找到依照目前排列的 lca 的下一個子樹的 root  r，將以 r 為 root 的子樹中第一個大於 r 的 node n  跟 r 交換，最後把以 n 為 root 的子樹的 node 做 reverse，這樣得到的就是以 n 為首的最小字典排列，也就是當前排列的下一個排列。

完整程式碼:

class Solution {

public:

    void nextPermutation(vector<int>& nums) {

        // find lowest common ancestor (actually, lca here is the next element of LCA)

        int lca = -1;

        for (int i = nums.size()-2; i >= 0; i--) {

            if (nums[i] < nums[i + 1]) {

                lca = i;

                break;

            }

        }

        // nums is in decreasing order ( largest lexicographically order ) 

        if (lca == -1) {

            reverse(nums.begin(), nums.end());

        }

        else {

            for (int i = nums.size()-1; i >= 0; i--) {

                if (nums[i] > nums[lca]) {

                    swap(nums[i], nums[lca]);

                    break;

                }

            }

            reverse(nums.begin() + lca + 1, nums.end());

        }

    }

};