【重点】【特例】31.下一个排列-CSDN博客

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/135252930

法1：找规律

在这里插入图片描述

Python

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        small = big = -1
        n = len(nums)
        for i in range(n-2, -1, -1):
            if nums[i] < nums[i+1]:
                small = i
                break
        if small == -1:
            self.my_reverse(0, n-1, nums)
        else:
            big = small + 1
            for i in range(big, n):
                if nums[i] > nums[small]:
                    big = i
            nums[small], nums[big] = nums[big], nums[small]
            self.my_reverse(small+1, n-1, nums)
    
    def my_reverse(self, start, end, nums):
        l, r = start, end
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

Java

class Solution {
    public void nextPermutation(int[] nums) {
        int small = -1, big = -1;
        for (int i = nums.length - 2; i >= 0; --i) {
            if (nums[i] < nums[i + 1]) {
                small = i;
                break;
            }
        }
        if (small == -1) {
            reverse(0, nums.length - 1, nums);
        } else {
            big = small + 1;
            for (int i = big; i < nums.length; ++i) {
                if (nums[i] > nums[small]) {
                    big = i;
                }
            }
            swap(small, big, nums);
            reverse(small + 1, nums.length - 1, nums);
        }
    }

    public void reverse(int i, int j, int[] nums) {
        while (i < j) {
            swap(i, j, nums);
            ++i;
            --j;
        }
    }

    public void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}