2025年- H94-Lc202-- 31.下一个排列(技巧）--Java版

1.题目描述

2.思路

给定一个整数数组 nums，找出它的下一个字典序排列（即比当前排列“刚好大一点”的排列）。
如果不存在下一个排列（即已是最大排列），则返回最小排列（升序排列）。

比如初始数组是[1,2,3]，所以对于第一个位置有3种可能，对于第二个位置有2种可能，最后一个位置有1种可能，所以总共有3*2=6种。
从小到大的排序：
【1，2，3】、【1，3，2】、【2，1，3】、【2，3，1】，【3，1，2】，【3，2，1】
但是要求按字典序大小，查找下一个排列的数
思路可以参考全排列
思路2:
（1）找从右往左第一个变大的地方
（2）在后面找一个刚比它大的数交换
（3）然后把后面升序排列（让它变最小）

3.代码实现

class Solution {
    public void nextPermutation(int[] nums) {
        int i=nums.length-2;
        while(i>=0&&nums[i]>=nums[i+1])
        {
            i--;
        }
        if(i>=0)
        {
            int j=nums.length-1;
            while(j>=0&&nums[i]>=nums[j])
            {
                j--;
            }
            swap(nums,i,j);
        }
        reverse(nums,i+1);
        
    }
    public void swap(int[] nums,int i,int j)
    {
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
    public void reverse(int[] nums,int start)
    {
        int left=start;
        int right=nums.length-1;
        while(left<right)
        {
            swap(nums,left,right);
            left++;
            right--;
        }
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        // 示例：[1, 3, 5, 4, 2]
        // 下一个排列是：[1, 4, 2, 3, 5]

        // 从后往前找第一个下降的位置（即 nums[i] < nums[i+1]）
        int i = nums.length - 2;  // 从倒数第二个位置开始
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;  // 找到第一个 "升序对" 的左边那个数
        }

        // 如果找到了这样的 i（说明当前排列不是最大的）
        if (i >= 0) {
            // 从后往前找第一个比 nums[i] 大的元素
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            // 交换 nums[i] 和 nums[j]
            swap(nums, i, j);
        }

        // 把 i+1 之后的部分反转，使它成为最小的排列（升序）
        reverse(nums, i + 1);
    }

    // 交换数组中下标 i 和 j 的两个元素
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 反转数组中从 start 到末尾的元素（原地升序）
    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}