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

发布于:2025-07-10 ⋅ 阅读:(14) ⋅ 点赞:(0)

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--;
        }
    }
}


网站公告

今日签到

点亮在社区的每一天
去签到