31. Next Permutation

problem description

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

algorithm thought

我们通过枚举法是可以直接枚举出所有排列的，但是这样太慢，并且排列直接明显有自己的规律。查询维基百科可以知道下一个排列的定义

1. Find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, just reverse nums and done.

2. Find the largest index l > k such that nums[k] < nums[l].

3. Swap nums[k] and nums[l].

4. Reverse the sub-array nums[k + 1:].

直接代码实现

code

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
    	int n = nums.size(), k, l;
    	for (k = n - 2; k >= 0; k--) {
            if (nums[k] < nums[k + 1]) {
                break;
            }
        }
    	if (k < 0) {
    	    reverse(nums.begin(), nums.end());
    	} else {
    	    for (l = n - 1; l > k; l--) {
                if (nums[l] > nums[k]) {
                    break;
                }
            } 
    	    swap(nums[k], nums[l]);
    	    reverse(nums.begin() + k + 1, nums.end());
        }
    }
}; 

algorithm analysis

最坏情况下，时间复杂度是O(n).最佳情况下，时间复杂度是O(1)