【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.不存在直接 reverseif(i==-1){int L = 0;int R = len;while(L<=R){swap(nums,L++,R--);}return ;}// 3.找交换点 jfor(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;}
}

---

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 找不到直reverseif(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]+" ");}}
}