[数据结构与算法]leetcode31.下一个排列——学习笔记

题目：力扣https://leetcode-cn.com/problems/next-permutation/

class Solution {
    public void nextPermutation(int[] nums) {
        int length = nums.length;
        for (int a=length-1;a>0;a--) {
                if (nums[a]>nums[a-1]) {
                    Arrays.sort(nums,a,length);
                    for (int b=a;b<length;b++) {
                        if (nums[b]>nums[a-1]) {
                            int temp = nums[b];
                            nums[b] = nums[a-1];
                            nums[a-1] = temp;
                            return;
                        }
                    }
                }
            }
    	Arrays.sort(nums);
		return;  
    }
 }

?

? 思路：题目的意思是：给定一个数字序列，通过一定的算法找到一个新的数字排序，这个排序的值需要大于题目给定排序的值；若找不到这个新的排序，则返回值最小的排序。若达到上述要求，则有一下几条要求：

? ? ? ? （1）将尽可能小的“大数”与前面的“小数”交换

? ? ? ? （2）尽量在低位进行交换

? ? ? ? （3）将“大数”换到前面后，需要将“大数”后面所有数重置为升序。

1.获取题目给定排序的长度。

int length = nums.length;

2.a为需要操作位置的下标，从后往前遍历，对满足条件的位置进行操作（具体步骤见后）。

for (int a=length-1;a>0;a--) {
    //......
    }

3.如果a下标对应的数为“大数”，a-1对应的数为“小数”，即表示可以进行换位操作。在换位操作进行之前，需要对a位置及以后的数进行升序排序（确保数组的增幅最小）。

if (nums[a]>nums[a-1]) {
    Arrays.sort(nums,a,length);
}

4.b的位置a所处的位置，从b的位置开始往后找找到比a-1处的值大的数则调换位置。完成位置调换的操作后，返回即可。

if (nums[a]>nums[a-1]) {
    Arrays.sort(nums,a,length);
    for (int b=a;b<length;b++) {
        if (nums[b]>nums[a-1]) {
            int temp = nums[b];
            nums[b] = nums[a-1];
            nums[a-1] = temp;
            return;
        }
    }
}

5.若此时的排序已经是最大的排序，找不到更大的排序了，则返回值最小的排序，即将给定数组按升序排序，返回。

Arrays.sort(nums);
return;