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版本

繁夜

发表评论


:[微笑]::[撇嘴]::[色]::[发呆]::[得意]::[流泪]::[害羞]::[闭嘴]::[睡]::[大哭]::[尴尬]::[发怒]::[调皮]::[呲牙]::[惊讶]::[难过]::[酷]::[冷汗]::[抓狂]::[吐]::[偷笑]::[可爱]::[白眼]::[傲慢]::[饥饿]::[困]::[惊恐]::[流汗]::[憨笑]::[大兵]::[奋斗]::[咒骂]::[疑问]::[嘘...]::[晕]::[折磨]::[衰]::[骷髅]::[敲打]::[再见]::[擦汗]::[抠鼻]::[鼓掌]::[糗大了]::[坏笑]::[左哼哼]::[右哼哼]::[哈欠]::[鄙视]::[委屈]::[快哭了]::[阴险]::[亲亲]::[吓]::[可怜]::[笑哭]::[doge]::[泪奔]::[无奈]::[托腮]::[斜眼笑]::[喷血]::[惊喜]::[骚扰]::[小纠结]::[我最美]::[羊驼]::[幽灵]::[吃]::[OK]::[爱你]::[抱拳]::[勾引]::[强]::[弱]::[拳头]::[爱心]::[喝彩]::[西瓜]::[啤酒]::[玫瑰]::[凋谢]::[礼物]::[拥抱]::[月亮]::[菊花]::[棒棒糖]::[蛋]::[刀]::[菜刀]::[炸弹]::[手枪]:

刷新评论