Java实现Next Permutation（下一个排列）出错，求问题排查

你的代码存在几处关键逻辑错误，导致无法正确生成下一个排列，以下是具体问题和修正方案：

错误点梳理 #

• 初始值设置错误：ind初始化为1是不合理的，应该初始化为-1，用来标记是否找到数组中第一个从右往左数的升序对（即nums[i] < nums[i+1]）。如果数组完全是降序排列，ind会保持-1，此时需要反转整个数组得到最小排列。
• 无效循环与错误反转：原代码中第二个for循环完全多余，且当ind == -1时，错误地执行了多次范围错误的反转操作。正确的做法是直接反转整个数组，之后终止后续流程。
• 反转范围错误：原代码最后执行reverse(nums,0,n-1)会反转整个数组，而正确逻辑是在找到ind并完成交换后，仅反转ind+1到数组末尾的部分，这部分原本是降序，反转后变为升序，才能得到下一个排列。
• 逻辑顺序错误：当ind == -1时，处理完反转后应该直接结束函数，否则会继续执行后面的交换和反转步骤，破坏结果。

修正后的代码 #

class Solution {
    public void nextPermutation(int[] nums) {
        int ind = -1;
        int n = nums.length;
        // 从右往左找第一个升序对的左索引
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                ind = i;
                break;
            }
        }
        // 如果是完全降序，直接反转整个数组
        if (ind == -1) {
            reverse(nums, 0, n - 1);
            return;
        }
        // 从右往左找第一个大于nums[ind]的元素并交换
        for (int j = n - 1; j > ind; j--) {
            if (nums[j] > nums[ind]) {
                swap(nums, j, ind);
                break;
            }
        }
        // 反转ind+1到末尾的部分，得到升序序列
        reverse(nums, ind + 1, n - 1);
    }
    
    public static void swap(int n[], int i, int j) {
        int temp = n[i];
        n[i] = n[j];
        n[j] = temp;
    }
    
    public static void reverse(int n[], int i, int j) {
        while (i < j) {
            swap(n, i, j);
            i++;
            j--;
        }
    }
}

修正说明 #

1. 修正ind初始值为-1，确保能正确识别完全降序的情况。
2. 当ind == -1时，直接反转整个数组并返回，避免后续不必要的操作。
3. 交换完成后，仅反转ind+1到末尾的部分，保证这部分变为升序，符合下一个排列的要求。
4. 移除了原代码中多余的循环和错误的反转逻辑，精简了流程。

内容的提问来源于stack exchange，提问作者Pari Patel