知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 46 - 下一个排列 ## 题目(LeetCode 31) 实现获取下一个排列的函数,将数字重新排列成字典序中下一个更大的排列。 ## 解法 ```java class Solution { public void nextPermutation(int[] nums) { int i = nums.length - 2; // 1. 从后往前找第一个下降的位置 while (i >= 0 && nums[i] >= nums[i + 1]) i--; if (i >= 0) { // 2. 从后往前找第一个比 nums[i] 大的 int j = nums.length - 1; while (nums[j] <= nums[i]) j--; swap(nums, i, j); } // 3. 反转 i+1 到末尾 reverse(nums, i + 1, nums.length - 1); } private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } private void reverse(int[] a, int l, int r) { while (l < r) swap(a, l++, r--); } } ``` ## 复杂度 - 时间 O(n),空间 O(1) ## 一句话总结 从后往前找第一个下降点,和后面刚好比它大的交换,再反转后面部分。 ## 说明 下一个排列的三步法(找下降点 → 找刚好大的数交换 → 反转后缀)是唯一 O(n) 时间 O(1) 空间的解法,且是原地操作。没有更优的替代方案。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入