31. Next Permutation

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.

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

先從數列的尾巴開始向前搜尋第一個遞減的數字(index i)，然後再從尾巴搜尋第一個大於前面搜尋到的那個數字(index j)，兩者互換之後將第一個搜尋到的數字後方的數字反轉。 e.g. [1, 2, 5, 4, 3, 1] 從後向前搜尋第一個遞減的數字是2(i = 1)，從後向前搜尋第一個比2大的數字是3(j = 4)，互換之後變成[1, 3, 5, 4, 2, 1]，再把index = 1之後的數列反轉，從index = 2開始反轉，最後變成[1, 3, 1, 2, 4, 5]。

void nextPermutation(vector<int>& nums) { // time: O(n); space: O(1)
    int n = nums.size();
    for (int i = n - 2; i >= 0; --i) {
        if (nums[i] < nums[i + 1]) {
            int j;
            for (j = n - 1; j > i; --j) {
                if (nums[j] > nums[i]) break;
            }
            swap(nums[i], nums[j]);
            reverse(nums.begin() + i + 1, nums.end());
            return;
        }
    }
    reverse(nums.begin(), nums.end());
}

void nextPermutation(vector<int>& nums) { // time: O(n); space: O(1)
    int n = nums.size(), i = n - 2, j = n - 1;
    // Search from the end to find the first element which is not ascending
    while (i >= 0 && nums[i] >= nums[i + 1]) --i;
    if (i >= 0) {
        // Search from the end to find the first element which is larger than nums[i]
        while (nums[i] >= nums[j]) --j;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}