LeetCode: 31. Next Permutation

引言

题目链接:https://leetcode.com/problems/next-permutation/

题目大意

给出一个序列实现下一个排列,它将数字重新排列成满足字典序的下一个更大的数字排列

如果下一个排列不可能(已经是最大的了),则必须将其重新排列为尽可能低的顺序(即按升序排序)

Hint

更换必须就地,并且只使用恒定的额外内存

  • Example

题解

此题其实求解下一个全排列

假设集合nums当前全排列情况为 [3, 7, 6, 2, 5, 4, 3, 1]求取下一个排列的步骤如下:

步骤解读:

  1. 从后向前查找第一个相邻元素对(i,j),并且满足nums[i] < nums[j]。显然,此时从j到end必然是降序。
  2. 在[j,end)中寻找一个最小的k使其满足nums[i] < nums[k]。由于[j,end)是降序的,所以必然存在一个k满足上面条件;并且可以从后向前查找第一个满足nums[i] < nums[k]关系的k,此时的k必是待找的k。
  3. 将i与k交换。此时,i处变成比i大的最小元素,因为下一个全排列必须是与当前排列按照升序排序相邻的排列,故选择最小的元素替代i,交换后的[j,end)仍然满足降序排序。因为在(k,end)中必然小于i,在[j,k)中必然大于k,并且大于i。
  4. 逆置[j,end),由于此时[j,end)是降序的,故将其逆置,最终获得下一个全排列。

Hint:如果在步骤1找不到符合的相邻元素对,即此时i=begin,则说明当前[begin,end)为一个降序顺序,即无下一个全排列,按照题意直接将整个排列逆置成升序

复杂度

时间复杂度 O(n)

空间复杂度 O(1)

AC代码

c++版本

go版本


繁夜