网站开发用什么编辑器好点,装修公司的收费标准,asp.net jsp 网站开发,工程施工合同免费版文章目录 1. 题目2. 思路及代码实现详解#xff08;Python#xff09;2.1 两遍扫描 1. 题目
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如#xff0c; a r r [ 1 , 2 , 3 ] arr [1,2,3] arr[1,2,3] #xff0c;以下这些都可以视作 a r r arr arr… 文章目录 1. 题目2. 思路及代码实现详解Python2.1 两遍扫描 1. 题目
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如 a r r [ 1 , 2 , 3 ] arr [1,2,3] arr[1,2,3] 以下这些都可以视作 a r r arr arr 的排列 [ 1 , 2 , 3 ] 、 [ 1 , 3 , 2 ] 、 [ 3 , 1 , 2 ] 、 [ 2 , 3 , 1 ] [1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] [1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地如果数组的所有排列根据其字典顺序从小到大排列在一个容器中那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列那么这个数组必须重排为字典序最小的排列即其元素按升序排列。
例如 a r r [ 1 , 2 , 3 ] arr [1,2,3] arr[1,2,3] 的下一个排列是 [ 1 , 3 , 2 ] [1,3,2] [1,3,2] 。类似地 a r r [ 2 , 3 , 1 ] arr [2,3,1] arr[2,3,1] 的下一个排列是 [ 3 , 1 , 2 ] [3,1,2] [3,1,2] 。而 a r r [ 3 , 2 , 1 ] arr [3,2,1] arr[3,2,1] 的下一个排列是 [ 1 , 2 , 3 ] [1,2,3] [1,2,3] 因为 [ 3 , 2 , 1 ] [3,2,1] [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 n u m s nums nums 找出 n u m s nums nums 的下一个排列。
必须 原地 修改只允许使用额外常数空间。
示例 1
输入 n u m s [ 1 , 2 , 3 ] nums [1,2,3] nums[1,2,3] 输出 [ 1 , 3 , 2 ] [1,3,2] [1,3,2]
示例 2
输入 n u m s [ 3 , 2 , 1 ] nums [3,2,1] nums[3,2,1] 输出 [ 1 , 2 , 3 ] [1,2,3] [1,2,3]
示例 3
输入 n u m s [ 1 , 1 , 5 ] nums [1,1,5] nums[1,1,5] 输出 [ 1 , 5 , 1 ] [1,5,1] [1,5,1] 提示 1 n u m s . l e n g t h 100 1 nums.length 100 1nums.length100 0 n u m s [ i ] 100 0 nums[i] 100 0nums[i]100
2. 思路及代码实现详解Python
本题要求实现一个算法将给定数字序列重新排列成字典序中下一个更大的排列。
以数字序列 [ 1 , 2 , 3 ] [1,2,3] [1,2,3] 为例其排列按照字典序依次为 [ 1 , 2 , 3 ] [ 1 , 3 , 2 ] [ 2 , 1 , 3 ] [ 2 , 3 , 1 ] [ 3 , 1 , 2 ] [ 3 , 2 , 1 ] \begin{aligned} [1,2,3]\\ [1,3,2]\\ [2,1,3]\\ [2,3,1]\\ [3,1,2]\\ [3,2,1] \end{aligned} [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
这样排列 [ 2 , 3 , 1 ] [2,3,1] [2,3,1] 的下一个排列即为 [ 3 , 1 , 2 ] [3,1,2] [3,1,2]。特别的最大的排列 [ 3 , 2 , 1 ] [3,2,1] [3,2,1] 的下一个排列为最小的排列 [ 1 , 2 , 3 ] [1,2,3] [1,2,3]。
2.1 两遍扫描
注意到下一个排列总是比当前排列要大除非该排列已经是最大的排列。我们希望找到一种方法能够找到一个大于当前序列的新序列且变大的幅度尽可能小。具体地 我们需要将一个左边的「较小数」与一个右边的「较大数」交换以能够让当前排列变大从而得到下一个排列。 同时我们要让这个「较小数」尽量靠右而「较大数」尽可能小。当交换完成后「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下使变大的幅度尽可能小。
以排列 [ 4 , 5 , 2 , 6 , 3 , 1 ] [4,5,2,6,3,1] [4,5,2,6,3,1] 为例 我们能找到的符合条件的一对「较小数」与「较大数」的组合为 2 2 2 与 3 3 3满足「较小数」尽量靠右而「较大数」尽可能小这里的「较大数」要比「较小数」大且增大幅度尽量小从右向左找到第一个非增的值即为「较小数」。 当我们完成交换后排列变为 [ 4 , 5 , 3 , 6 , 2 , 1 ] [4,5,3,6,2,1] [4,5,3,6,2,1]此时我们可以重排「较小数」右边的序列序列变为 [ 4 , 5 , 3 , 1 , 2 , 6 ] [4,5,3,1,2,6] [4,5,3,1,2,6]。
具体地我们这样描述该算法对于长度为 n n n 的排列 a a a 首先从后向前查找第一个顺序对 ( i , i 1 ) (i,i1) (i,i1)满足 a [ i ] a [ i 1 ] a[i]a[i1] a[i]a[i1]。这样「较小数」即为 a [ i ] a[i] a[i]。此时 [ i 1 , n ) [i1,n) [i1,n) 必然是下降序列。 如果找到了顺序对那么在区间 [ i 1 , n ) [i1,n) [i1,n) 中从后向前查找第一个元素 j j j 满足 a [ i ] a [ j ] a[i]a[j] a[i]a[j]。这样「较大数」即为 a [ j ] a[j] a[j]且显然 a [ j − 1 ] ≥ a [ j ] a [ i ] ≥ a [ j 1 ] a[j-1]\geq a[j]a[i]\geq a[j1] a[j−1]≥a[j]a[i]≥a[j1]这保证了「较大数」向前交换后右边的序列仍旧是以降序排列的。 交换 a [ i ] a[i] a[i] 与 a [ j ] a[j] a[j]此时区间 [ i 1 , n ) [i1,n) [i1,n) 仍为降序。我们可以直接使用双指针反转区间 [ i 1 , n ) [i1,n) [i1,n) 使其变为升序而无需对该区间进行排序。
该算法在最坏情况下找到「较小数」需要经过给定序列长度 N N N 的次数的比较以及进行的反转操作也是 N N N 量级的计算复杂度因此总的时间渐进复杂度为 O ( N ) O(N) O(N)而空间复杂度为仅存放待交换整数的索引位置复杂度为 O ( 1 ) O(1) O(1)。
class Solution:def nextPermutation(self, nums: List[int]) - None:i len(nums) - 2while i 0 and nums[i] nums[i 1]:i - 1if i 0:j len(nums) - 1while j 0 and nums[i] nums[j]:j - 1nums[i], nums[j] nums[j], nums[i]left, right i 1, len(nums) - 1while left right:nums[left], nums[right] nums[right], nums[left]left 1right - 1执行用时29 ms 消耗内存16.40 MB
题解来源力扣官方题解
