题目描述
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
示例一:
1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
思路
1.其实本题中的下一个排列就是比当前数大的下一个数。
2.我们首先应该找到那对应该被交换的数字。
3.左边应该被交换的数字符合nums[i]<nums[i-1]的特征;右边应该被交换的数是刚好大于左边数字的最小数字,即j in (i+1,nums.length-1) && min(i+1,nums.length-1) && nums[j]>nums[i]。
4.我们交换数据后,将左边数字的右边进行从小到大排序即可。
例如:
1587624310 1.找到 2 为左边应该被交换位置的数 2.找到 3 为右边应该被交换位置的数 3.交换 2 和 3 的位置--->1587634210 4.升序排序 3 右边的数字 ---->1587630124
Java代码实现
public void nextPermutation(int[] nums) { int i = nums.length-2; //寻找左边的数 while(i>=0 && nums[i]>=nums[i+1]){ i--; } //寻找右边的数 if(i>=0){ int j = nums.length-1; while(nums[j]<=nums[i]){ j--; } swap(nums,i,j); } //因为右边的数交换完成后是降序的,所以直接翻转即可 reverseNums(nums,i+1,nums.length-1); } private void reverseNums(int[] nums,int left,int right){ while(left<right){ swap(nums,left++,right--); } } private void swap(int[] nums,int i,int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
Golang代码实现
func nextPermutation(nums []int) { i := 0 for i =len(nums)-2 ; i>=0 ; i--{ if nums[i] < nums[i+1] { for j := len(nums)-1; j>i;j--{ if nums[j] > nums[i] { swap(nums,i,j) break } } break } } reverseNums(nums,i+1,len(nums)-1) } func swap(nums []int,left int,right int){ temp := nums[left] nums[left] = nums[right] nums[right] = temp } func reverseNums(nums []int,left int,right int){ for left <= right { swap(nums,left,right) left++ right-- } }