[数据结构与算法]Leetcode P31

31. 下一个排列

1.思路

? 由题意得整数数组的 下一个排列 是指其整数的下一个字典序更大的排列，那么我们只需要按照字典序排序就可以了，首先我们从数组的最后一位开始向左查找，直到找到一个比数组最后一位的小的数组进行交换，然后从找到比数组最后一位下标小的数组下标+1到数组最后一位进行从小到大的排序就可以完成。

? 如果上述没有结束，那么就是数组的字典序列是最大的值，我们直接将数组sort即可。因为最大值的下一个就是最小值

2. Code

class Solution {
   public void nextPermutation(int[] nums) {
        //首先我们从数组的最后一位开始向左查找
        for (int i = nums.length-1; i >=0 ; i--) {
            for (int j = nums.length-1; j > i ; j--) {
                //直到找到一个比数组最后一位的小的数组进行交换
                if (nums[i] < nums[j]){
                    swap(nums,i,j);
                    //从找到比数组最后一位下标小的数组下标+1到数组最后一位进行从小到大的排序
                    Arrays.sort(nums,i+1,nums.length);
                    return;
                }
            }
        }
		
       //	?	如果上述没有结束，那么就是数组的字典序列是最大的值，我们直接将数组sort即可。因为最大值的下一个就是最小值
        Arrays.sort(nums);
    }

    public void swap(int[] nums,int x,int y){
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}