31.下一排列

给定一个数列,寻找按字典序排列比它大的下一数列,如果不存在比它大的数列,则寻找字典序最小的数列。

考虑两种情况:1.逆序数组不存在字典序比它大的情况,这时候返回升序数组即可。2.当不是逆序数组时呢?我们必然能找到一个顺序对,如 5 4 2 3 1 中 2 和 3 就是顺序的,它的下一排列是 5 4 3 1 2 。以这个例子为例,将顺序对中较大的数字放于较小的位置,并对接下来的数组做排序。如果存在多个顺序对?如 5 1 2 3 4 ,这时候要考虑哪个顺序对的前者最远, 这里最远的顺序对是 3 4 所以下一排列 5 1 2 4 3 ,再考虑如果前者一样呢, 如 5 4 1 2 3 ,这个例子里 1 2 和 1 3 都是顺序对,那就考虑后者较小的那个,以 1 2 来重排列。

总结:关键在于找顺序对,使用两个指针,first 用于指向顺序对的开头, second 用于指向比first 大的较小值。

找顺序对的主要思路是先寻找 first 只要后者大于前者就行。一直迭代自然会指向较后的顺序对。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 基础篇NumPy的主要对象是同种元素的多维数组。这是一个所有的元素都是一种类型、通过一个正整数元组索引的元素表格(...
    oyan99阅读 10,545评论 0 18
  • 前言 2. 实现 Singleton 3. 数组中重复的数字 4. 二维数组中的查找 5. 替换空格 6. 从尾到...
    Observer_____阅读 8,086评论 0 1
  • NumPy是Python中关于科学计算的一个类库,在这里简单介绍一下。 来源:https://docs.scipy...
    灰太狼_black阅读 4,980评论 0 5
  • 先决条件 在阅读这个教程之前,你多少需要知道点python。如果你想从新回忆下,请看看Python Tutoria...
    舒map阅读 7,410评论 1 13
  • 今天在106办公室听到有个老师托阳老师给一个家长找家教,辅导一个8岁的小男孩英语,再加晚上睡觉给他读故事听。他家条...
    果味卓v阅读 1,033评论 0 0