下一个排列[发挥主观能动性发现规律]

前言

有时候抛弃套路(共性)，发挥主观能动性，找到题的个性所在，挖掘其特点，见招拆招，才能解掉一个题。

一、下一个排列

二、逻辑分析与代码整理

package everyday.medium;

// 下一个排列
public class NextPermutation {
    
    /* target：把nums当作一个数，取下一个数。从后往前找，找到一对数，左 < 右，然后从后面的单调递增子数组交换一个稍大的数，然后翻转后面的单调递增子数组。 如果遍历完都没找到，那就是特殊情况，直接翻转。 */
    public void nextPermutation(int[] nums) {
    
        if (nums.length == 1) return;
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) --i;
        int begin = 0;//翻转开始处，默认全部翻转。
        // 当i >= 0时，需要确定新的翻转开始处。
        if (i >= 0) {
    
            // 交换以获取下一个序列
            // 寻找需要交换的数字
            int idx = nums.length - 1;
            while (nums[idx] <= nums[i]) idx--;
            // 交换两者，且 i + 1 到 nums.length - 1保持单调递减，直接翻转。
            int t = nums[i];
            nums[i] = nums[idx];
            nums[idx] = t;
            // 确定从那里开始翻转
            begin = i + 1;
        }
        // 翻转
        for (int j = 0; j < nums.length - begin >>> 1; j++) {
    
            int t = nums[begin + j];
            nums[begin + j] = nums[nums.length - 1 - j];
            nums[nums.length - 1 - j] = t;
        }
    }
}

总结

1）发挥主观能动性/思考力，发现问题个性，按逻辑写出代码，再整理逻辑代码。

参考文献

[1] LeetCode 下一个排列