【Hot100】LeetCode—31. 下一个排列

---

题目

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

---

1- 思路

技巧题，分为以下几个步骤

• ① 寻找拐点： i + 1 ：出现 nums[i+1] > nums[i] ，则 i + 1 就是拐点 从右向左遍历
  • 如果没有拐点，直接利用 L 指针和 R 指针，reverse 整个数组
• ② 寻找交换点：利用 j 寻找在 [i+1,len] 的区间内，第一个大于 nums[i] 的元素，定位为 j
• ③ 交换元素 i 和 j：直接利用 swap 交换
• ④ reverse区间 [i+1,len]：利用 L 和 R 双指针进行 reverse。

---

2- 实现

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

class Solution {
    public void nextPermutation(int[] nums) {
        //1. 找拐点
        int i,j;
        int len = nums.length-1;

        for(i = len-1;i>=0;i--){
            if(nums[i] < nums[i+1]) break;
        }

        // 2.不存在直接 reverse
        if(i==-1){
            int L = 0;
            int R = len;
            while(L<=R){
                swap(nums,L++,R--);
            }
            return ;
        }

        // 3.找交换点 j
        for(j = len;j>=i+1;j--){
            if(nums[i]<nums[j]) break;
        }
        swap(nums,i,j);

        // 4.revers[i+1,len]
        int L = i+1;
        int R = len;
        while(L<=R){
            swap(nums,L++,R--);
        }

    }

    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

---

3- ACM 实现

public class nextPermutation {

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

        // 1.1 找不到直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);

        // 3.reverse[i+1,len]
        int L = i+1;
        int R = len;
        while(L<=R){
            swap(nums,L++,R--);
        }
    }

    private 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();
        }
        nextPart(nums);
        System.out.println("结果是");
        for(int i = 0 ;i < n;i++){
            System.out.print(nums[i]+" ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55