31. 下一个排列

查看题目

中等

数组

中频

解法一：迭代法

时间复杂度：O(n) | 空间复杂度：O(1) | 推荐使用

动画演示

数组值:

准备就绪 - 输入数组值（用逗号分隔），然后点击开始

代码实现

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        // 从右向左找到第一个降序点
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            // 从右向左找到第一个大于 nums[i] 的元素
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            // 交换元素
            swap(nums, i, j);
        }
        // 反转后续部分
        reverse(nums, i + 1);
    }
    
    // 交换数组中的两个元素
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    // 反转数组从 start 到末尾的元素
    private void reverse(int[] nums, int start) {
        int end = nums.length - 1;
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

# Next Permutation 算法详解 ## 算法思路 Next Permutation 算法用于找到给定数字序列的下一个字典序排列。算法的核心步骤如下： 1. **找到降序点**：从右向左遍历数组，找到第一个位置 'i'，使得 'nums[i] < nums[i+1]'。这个位置是第一个可以调整的点。 2. **找到交换点**：从右向左遍历数组，找到第一个位置 'j'，使得 'nums[j] > nums[i]'。这个元素是用来与 'nums[i]' 交换的最小元素。 3. **交换元素**：交换 'nums[i]' 和 'nums[j]'，这样可以得到一个更大的排列。 4. **反转后续部分**：反转 'nums[i+1]' 到数组末尾的元素，使得这部分变为升序，从而得到最小的可能排列。 ## 算法分析 - **时间复杂度**：O(n)，其中 n 是数组的长度。最多需要两次遍历数组，以及一次反转操作，都是线性时间复杂度。 - **空间复杂度**：O(1)，只使用了常数级别的额外空间，没有使用额外的数据结构。 ## 示例 ### 示例 1 输入：nums = [1,2,3] 输出：[1,3,2] ### 示例 2 输入：nums = [3,2,1] 输出：[1,2,3]（因为这是最后一个排列，所以返回第一个排列） ### 示例 3 输入：nums = [1,1,5] 输出：[1,5,1] ## 实现细节 - 算法在原地修改数组，不需要返回值。 - 如果找不到降序点（即数组是降序排列的），则直接反转整个数组，得到最小的排列。 - 交换操作使用常数时间，反转操作使用线性时间。 ## 应用场景 Next Permutation 算法在以下场景中非常有用： 1. 生成排列组合 2. 解决字典序相关的问题 3. 密码学中的某些应用 4. 游戏开发中的某些算法