阅读量:0
目录
题目
- 原题连接：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; } } 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]+" "); } } } 