【CT】LeetCode手撕—31. 下一个排列

---

题目

• 原题连接：31. 下一个排列

---

1- 思路

思路

• ① 从右边找出一个尽可能大的数，和左边的数进行交换 ——> 交换后得到的数 就是 字典序更高
• ② 字典序高，但不代表其就是下一个 ——> 如何找下一个？
  • 左边的小数，尽可能靠右
  • 右边的大数，尽可能的小（比左边的小数大一点点）

目标

• ① 找到数组的拐点 ——> 从右向左遍历 ——> nums[i] < nums[i+1] 则找到了拐点 i+1
• ② 找到拐点右侧第一个 nums[i] 大的元素，此时记录 为 j ——> 从右向左遍历
• ③ 将元素 i 和 元素 j 交换，之后 sort(i+1,len-1)
• ④ 如果不存在拐点，此时直接 reverse 整个数组

---

2- 实现

⭐31. 下一个排列——题解思路

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length-1;
        int i = len-1,j;
        // 1. 找拐点
        for(; i>=0 ;i--){
            if(nums[i] < nums[i+1]) break;
        }

        // 最大序列直接 reverse
        if(i==-1){
            int L = 0;
            int R = len;
            while(L<=R){
                swap(nums,L++,R--);
            }
            return;
        }

        // 2. 有拐点
        for( j = len; j>=i+1 ; j--){
            if(nums[j] > nums[i]) break;
        }
        swap(nums,i,j);
        // 实现 Reverse
        int L = i+1;
        int R = len;
        while(L<=R){
            swap(nums,L++,R--);
        }
        return;
    }

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

---

3- ACM 实现

public class nextPL {

    public static void nextPL(int[] nums){
        // 1.找拐点，从右往左
        int len = nums.length-1;
        int i ,j;
        for( i = len-1 ; i >= 0 ; i--){
            if(nums[i] < nums[i+1]) break;
        }

        if(i==-1){
            int L = 0;
            int R = len;
            while(L<=R){
                swap(nums,L++,R--);
            }
            return;
        }

        // 2. 找第一个小值
        for(j = len;j>=i+1;j--){
            if(nums[j] > nums[i]) break;
        }

        // 3. 先交换
        swap(nums,i,j);
        // 4. reverse
        int L = i+1;
        int R  = len;
        while(L<=R){
            swap(nums,L++,R--);
        }
        return;
    }

    // 定义 swap 函数
    public static void swap(int[] nums,int i ,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入数组长度");
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0;  i < n; i++){
            nums[i] = sc.nextInt();
        }
        nextPL(nums);
        System.out.println("下一个排列是");
        for(int i : nums){
            System.out.print(i+" ");
        }
    }
}

---

原文地址：https://blog.csdn.net/weixin_44382896/article/details/140171253

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！