LeetCode: 31. 下一个排列

[resse92]

思路：
找几个例子分析一下就可以得知

1. 从最后一个开始遍历，找到不是降序的第一个数字的索引，即为index
2. 从最后一个开始遍历，找到第一个比nums[index]大的第一个数字
3. 交换两个数字
4. 从index + 1开始，重新排序一下即可。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
    
    template<typename BidiIt>
    bool next_permutation(BidiIt first, BidiIt last) {
        
        const auto rfirst = reverse_iterator<BidiIt>(last);
        const auto rlast = reverse_iterator<BidiIt>(first);

        auto pivot = next(rfirst);

        while (pivot != rlast and !(*pivot < *prev(pivot)))
            ++pivot;

        if (pivot == rlast) {
            reverse(rfirst, rlast);
            return false;
        }

        auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot));

        swap(*change, *pivot);
        reverse(rfirst, pivot);
        return true;
    }
};

class Solution:
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        
        if length == 1:
            return
        
        if length == 2:
            nums[0], nums[1] = nums[1], nums[0]
            return
        
        index = length - 1
        last = nums[length - 1]
        # 遍历第一遍
        for i in range(length - 2, -1, -1):
            index = i
            if last > nums[i]:
                break
            last = nums[index]
        
        secondIndex = length
        # 遍历第二遍
        for i in range(length - 1, -1, -1):
            secondIndex = i
            if nums[i] > nums[index]:
                break
                
        if index == secondIndex:
            nums.sort()
            return
        print(index, secondIndex)
        nums[index], nums[secondIndex] = nums[secondIndex], nums[index]
        y = nums[index + 1: length]
        y.sort()
        nums[index + 1: length] = y