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

目录

• 题目
• 1- 思路
• 2- 实现
• • ⭐31. 下一个排列——题解思路
• 3- ACM 实现

题目

• 原题连接：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]+" ");         }     } }