做老师一些好的网站,carousel wordpress,西宁做网站君博推荐,网站建设推广运营Problem: 31. 下一个排列 文章目录整体思路完整代码时空复杂度时间复杂度#xff1a;O(N)空间复杂度#xff1a;O(1)整体思路
这段代码旨在解决经典的 “下一个排列” (Next Permutation) 问题。问题要求重新排列一个整数数组#xff0c;使其变为字典序上的下一个更大的排列… Problem: 31. 下一个排列 文章目录整体思路完整代码时空复杂度时间复杂度O(N)空间复杂度O(1)整体思路
这段代码旨在解决经典的 “下一个排列” (Next Permutation) 问题。问题要求重新排列一个整数数组使其变为字典序上的下一个更大的排列。如果不存在更大的排列即数组已经是降序排列则将其重新排列为最小的排列即升序排列。这个操作必须在原地完成只使用常数级的额外空间。
该算法是一种非常精巧的、基于观察的单次遍历解法。其核心思想是要找到下一个更大的排列我们需要从右向左找到第一个“破坏”降序趋势的数字然后用一个比它稍大的数替换它并对后面的部分进行排序以得到最小的增量。
算法的逻辑步骤可以分解为以下四步 从右向左查找第一个“升序”对 (找到“小数”) 算法从数组的倒数第二个元素 (i n - 2) 开始向左扫描。它寻找第一个满足 nums[i] nums[i 1] 的索引 i。为什么 从右边看只要 nums[i] nums[i1] 持续成立说明 [i, n-1] 这个后缀是一个降序或非增序序列。一个降序序列已经是它所能构成的最大排列。为了找到一个更大的排列我们必须在更左边找到一个可以增大的“枢轴点”。这个 nums[i] 就是这个枢轴点我们称之为“小数”。 从右向左查找第一个比“小数”大的数 (找到“大数”) 在找到 i 之后算法再从数组的最右端 (j n - 1) 开始向左扫描。它寻找第一个满足 nums[j] nums[i] 的索引 j。为什么 我们需要用一个比 nums[i] 大的数来替换它以确保新的排列比旧的大。为了让这个增量尽可能小以得到“下一个”排列我们应该选择那个在后缀 [i1, n-1] 中比 nums[i] 大的数里面最小的那个。由于后缀 [i1, n-1] 是降序的所以从右向左找到的第一个比 nums[i] 大的数 nums[j] 恰好就是这个“稍大”的数。 交换“小数”和“大数” 找到 i 和 j 后交换 nums[i] 和 nums[j] 的值。效果此时[0, i] 这部分已经确保了新的排列比原来的大。 反转“小数”位置之后的所有数 在交换之后后缀 [i1, n-1] 仍然保持降序。为什么 为了得到紧邻的下一个排列我们需要让 [i1, n-1] 这部分变为它所能构成的最小排列。一个降序序列的最小排列就是将其变为升序。因此算法将 [i1, n-1] 这个区间进行反转使其变为升序。 特殊情况 如果步骤1中的 while 循环结束后 i 变成了负数这说明整个数组是完全降序的如 [3, 2, 1]。此时不存在更大的排列算法会跳过步骤2和3直接执行步骤4反转整个数组从索引0开始得到最小的排列升序。
完整代码
class Solution {/*** 找到并原地修改数组为下一个更大的字典序排列。* param nums 整数数组*/public void nextPermutation(int[] nums) {int n nums.length;// 步骤 1: 从右向左查找第一个“升序”对 (nums[i] nums[i1])// i 是这个“小数”的索引。int i n - 2;while (i 0 nums[i] nums[i 1]) {i--;}// 如果 i 0, 说明找到了这样的“小数”即数组不是完全降序的。if (i 0) {// 步骤 2: 从右向左查找第一个比 nums[i] 大的数// j 是这个“大数”的索引。int j n - 1;while (nums[i] nums[j]) {j--;}// 步骤 3: 交换“小数”和“大数”swap(nums, i, j);}// 步骤 4: 反转“小数”位置之后的所有数// 如果 i 0 (数组完全降序)这将反转整个数组得到最小排列。// 否则这将使交换后的后缀变为最小排列。reverse(nums, i 1, n - 1);}/*** 辅助函数交换数组中两个索引位置的元素。*/private void swap(int[] nums, int i, int j) {int t nums[i];nums[i] nums[j];nums[j] t;}/*** 辅助函数原地反转数组的指定区间 [left, right]。*/private void reverse(int[] nums, int left, int right) {while (left right) {swap(nums, left, right--);}}
}时空复杂度
时间复杂度O(N)
查找 i第一个 while 循环最多扫描整个数组一次。在最坏情况下时间复杂度为 O(N)。查找 j第二个 while 循环最多扫描整个数组一次。在最坏情况下时间复杂度为 O(N)。交换swap 操作是 O(1)。反转reverse 函数最多需要遍历 N/2 次交换其操作的元素数量与 N 呈线性关系。在最坏情况下时间复杂度为 O(N)。
综合分析 整个算法由几次独立的、不嵌套的线性扫描组成。总的时间复杂度是 O(N) O(N) O(N) O(N)。
空间复杂度O(1)
主要存储开销该算法没有创建任何与输入规模 N 成比例的新的数据结构。辅助变量只使用了 n, i, j, t, left, right 等几个固定数量的整型变量。
综合分析 算法的所有操作都是在原数组上进行的in-place所需的额外辅助空间是常数级别的。因此其空间复杂度为 O(1)。 参考灵神
