牛客网:https://leetcode-cn.com/problems/next-permutation

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

 

这个题可以自己出4个数和5个数的例子,三个数比较难找到规律:

1,2,3,4,5

1,2,3,5,4

1,2,4,3,5

1,2,4,5,3

仔细看变红的一行和前一行粉色的:这是从后

1。找到第一个比前一个数大的数,然后从这开始到最后进行升序排列,来保证是大一丢丢,如我举例的粉色到红色,先找到5的位置,

      然后从5开始升序排列变为临时序列:1,2,3,4,5

2.   然后在找到的位置的前一个位置即3的位置替换为被排好序的比三大的数,这样保证比原来大,即

      1,2,3,4,5 ->  1 2 4 3 5

 

public void nextPermutation(int[] nums) {
		if(nums.length<=1)return;//如果长度小于等于1不用找了
		for(int i=nums.length-1;i>=1;--i) {
			if(nums[i]>nums[i-1])
			{	
				Arrays.sort(nums, i, nums.length);//进行我们的排序,保证后面找时只大一丢丢

				for(int j=i;j<nums.length;++j) {

					if(nums[j]>nums[i-1]) {//找到第一个比i-1位置大的数,保证较大
						int tmp = nums[j];
						nums[j] = nums[i-1];
						nums[i-1] = tmp;
						return ;
					}
				}
				return ;
			}
		}
		Arrays.sort(nums);
		return ;
         
 			
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。