leetcode31-下一个排列

原题

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3][1,3,2][3,1,2][2,3,1]
    整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。

  • 例如,arr = [1,2,3] 的下一个排列是 [1,3,2]

  • 类似地,arr = [2,3,1] 的下一个排列是 [3,1,2]
  • arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。
    给你一个整数数组 nums ,找出 nums 的下一个排列。

必须 原地 修改,只允许使用额外常数空间。

 

示例 1:

输入: nums = [1,2,3] 输出: [1,3,2]

示例 2:

输入: nums = [3,2,1] 输出: [1,2,3]

示例 3:

输入: nums = [1,1,5] 输出: [1,5,1]  

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

解法

思想

找到最靠近右边,相邻正序的两个数字,将第一位与其后面出现的最靠右的且大于它的数字作交换,然后再对后面的数字逆序操作。

代码

func nextPermutation(nums []int)  {
    var left = -1
    var right = -1
    for i := 0; i< len(nums); i++{
        if i!=len(nums)-1 && nums[i+1]-nums[i] > 0{
            left = i
        }else if left != -1{
            if nums[i]>nums[left]&&(i == len(nums)-1||nums[i+1]<=nums[left]){
                right = i
            }
        }
    }

    if left != -1{
        nums[left], nums[right] = nums[right], nums[left]
    }

    start := left+1
    end := len(nums) - 1
    for start < end{
        nums[start], nums[end] = nums[end],nums[start]
        start ++
        end --
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode31-%e4%b8%8b%e4%b8%80%e4%b8%aa%e6%8e%92%e5%88%97/

(1)
彭晨涛彭晨涛管理者
上一篇 2020年6月26日
下一篇 2024年3月18日

相关推荐

  • leetcode144-二叉树的前序遍历

    原题 给定一个二叉树,返回它的 前序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    0120
  • leetcode1-两数之和

    原题 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能…

    算法 2019年12月20日
    080
  • leetcode55-跳跃游戏

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例1: 输入: [2,3,1…

    算法 2020年2月9日
    070
  • leetcode347-前K个高频元素

    原题 给定一个非空的整数数组,返回其中出现频率前 k 高的元素。 示例1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例2: 输入: n…

    算法 2019年12月28日
    0140
  • 程序员面试金典08.11-硬币

    原题(来源Leetcode) 硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007) 示…

    算法 2020年4月23日
    0160
  • leetcode225--用队列实现栈

    原题 使用队列实现栈的下列操作: push(x) – 元素 x 入栈 pop() – 移除栈顶元素 top() – 获取栈顶元素 empty() – 返回栈是否为空 注意: 你只能…

    算法 2019年12月13日
    0100
  • leetcode38-外观数列

    原题 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 被读作…

    算法 2020年4月30日
    0290
  • leetcode79-单词搜索

    原题 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格…

    算法 2020年4月12日
    0130
  • leetcode24-两两交换链表中的节点

    原题 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例: 给定 1->2->3->…

    算法 2020年1月20日
    0200
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04560

发表回复

登录后才能评论

评论列表(3条)