0031._Next_Permutatio.md

31.Next Permutatio

难度Medium

刷题内容

原题连接

• https://leetcode.com/problems/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

思路 - 时间复杂度: O(n)- 空间复杂度: O(1)******

我们可以用两个指针表示需要交换的两个数，遍历数组。这题的最坏的情况下，数组降序排列，排序算法的复杂度也是O(n)。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n1 = 0,n2 = 0;
        for(int i = 1;i < nums.size();++i)
            if(nums[i] > nums[n2])
            {
                n1 = n2;
                n2 = i;
            }
            else if((nums[i] < nums[n2] && nums[i] > nums[n1]) || nums[i] == nums[n2])
                n2 = i;
            else if(nums[i] <= nums[n1])
            {
                int j = i;
                for(;j < nums.size() - 1;++j)
                    if(nums[j + 1] > nums[j])
                    {
                        n1 = j;
                        n2 = j + 1;
                        break;
                    }
                i = j + 1;
            }
        if(n1 == n2)
            sort(nums.begin(),nums.end());
        else
        {
            swap(nums[n1],nums[n2]);
            sort(nums.begin() + n1 + 1,nums.end());
        }
    }
};