题解 | #下一个排列#

思路: 看注释吧，谢谢，我注释写得很详细，这里就不再重新写了(懒...)

import java.util.*;


public class Solution {  
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    // 自定义一个比较器，实现数组的逆序排序
    public class ComparaInverted implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return num2 - num1;
        }
    }
    public int[] nextPermutation (int[] nums) {
        
        Integer[] origin = new Integer[nums.length]; // 定义一个 Integer 数组，用于存放原始的数据
        Integer[] originCopy = new Integer[nums.length]; // 原始数据的备份
        for (int i = 0; i < nums.length; i++) { // 将原始的数据进行迁移
            origin[i] = nums[i];
            originCopy[i] = nums[i];
        }
        
        Arrays.sort(originCopy, new ComparaInverted()); // 将备份数据进行逆序排序
        if (Arrays.equals(originCopy, origin)) { // 如果原始数据逆序排序后等于原始数据，那么说明，原始数据是在整个字典序的最后面，我们需要返回的是整个字典序的第一个数据
            Arrays.sort(originCopy); // 将备份数据进行正序排序，即可得到字典序中的第一个数据
            int[] res = new int[originCopy.length]; // 定义一个 int 类型的整数数组，存放题目要求的返回结果
            for (int i = 0; i < originCopy.length; i++) {
                res[i] = originCopy[i];
            }
            return res;
        }
        else { // 如果原始数据逆序排序后不等于原始数据，那么，在字典序中，肯定存在着比原始数据要大的数据，返回比原始数据大一位的数据
            // 从原始数据的结尾开始遍历，找到位置 index，index 满足 origin[index] > origin[index - 1]
            int index = 0;
            for (int i = origin.length - 1; i > 0; i--) {
                if (origin[i] > origin[i - 1]) {
                    index = i;
                    break;
                }
            }
            // 此时，我们已经找到了 index 和 origin[index - 1]，接下来，我们要做的是，在 index - 1 这个位置的右边部分，找到所有比 origin[index - 1] 大的数字中，最小的那一个数字
            int minP = 0; // 定义一个指针，用于指向上述的数字所在的位置索引
            int minVal = origin[index]; // 定义一个整型变量，用于存放最小的那个数字，初始化为 origin[index](注: origin[index]不一定是我们要找的那个最小的数字，我们希望的是，找到的那个数字的大小为 origin[index - 1] < num <= origin[index])
            for (int i = origin.length - 1; i >= index; i--) {
                if (origin[i] > origin[index - 1] && origin[i] <= minVal) {
                    minP = i;
                    minVal = origin[i];
                }
            }
            // 最终，我们找到了这么一个数字的位置，然后，将这个位置上的数字与 origin[index - 1] 上的数字交换，同时，将以 index 往右的数字按照正序排列
            int swap = origin[index - 1];
            origin[index - 1] = origin[minP];
            origin[minP] = swap;
            Arrays.sort(origin, index, origin.length - 1);
            int[] res = new int[origin.length]; // 定义一个 int 类型的整型数组，存放题目要求的返回结果
            for (int i = 0; i < origin.length; i++) {
                res[i] = origin[i];
            }
            return res;
        }
    }
}