一、下一个排列
实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列(即,组合出下一个更大的整数)。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
示例 1:
输入:nums = [1,2,3]
输出:[1,3,2]
示例 2:
输入:nums = [3,2,1]
输出:[1,2,3]
示例 3:
输入:nums = [1,1,5]
输出:[1,5,1]
示例 4:
输入:nums = [1]
输出:[1]
1、先找较小值 nums[i] > nums[i + 1]就是较小值
2、找出较大值 nums[i] > nums[j]
3、把较大值和较小值进行交换
4、较大值后面的数 按照升序排列
package letcode; import java.util.Arrays; /** * 2021-9-17 * 下一个排列 */ public class LetCode1 { public static void main(String[] args) { int[] nums = {5,2,6,8,9,2,6,9,2,6,7}; LetCode1 letCode1 = new LetCode1(); letCode1.nextPermutation(nums); System.out.println(Arrays.toString(nums)); } /** * 主要思路 * 1、先找较小值 * 2、找出较大值 * 3、把较大值和较小值进行交换 * 4、较大值后面的数 按照升序排列 * @param nums */ public void nextPermutation(int[] nums) { int i = nums.length - 2; while ( i > 0 && nums[i] >= nums[i + 1]){ //从后往前排序找到 较小值 nums[i] > nums[i + 1]就是较小值 i--; } if(i > 0){ int j = nums.length - 1; while (j > 0 && nums[i] >= nums[j]){ // 找到较大值 nums[i] > nums[j] j--; } swap(nums,i,j); } sortRows(nums,i+1); } // 交换方法 public void swap(int[] nums, int i ,int j ){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } // 升序方法 public void sortRows(int[] nums,int start){ int left = start; int right = nums.length - 1; while ( left < right){ swap(nums,start,right); left++; right--; } } }