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日

相关推荐

  • leetcode503-下一个更大元素II

    原题 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,…

    算法 2020年2月1日
    0100
  • leetcode695-岛屿的最大面积

    原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围…

    算法 2020年3月15日
    01230
  • leetcode16-最接近的三数之和

    原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存…

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

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

    算法 2020年1月20日
    0200
  • leetcode26-删除排序数组中的重复项

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空…

    算法 2019年11月23日
    0190
  • leetcode1028-从先序遍历还原二叉树

    原题 我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处,我们输出 D 条短划线(其中 D 是该节点的深度),然后输出该节点的值。(如果节点的深度为 D,…

    2020年6月18日
    02410
  • leetcode1071-字符串的最大公因子

    原题 对于字符串 S 和 T,只有在 S = T + ... + T(T 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。 返回最长字符串 X,要求满足 X 能除尽 …

    算法 2020年3月12日
    0250
  • leetcode112-路径总和

    原题 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例:  给定如下二叉树,…

    算法 2020年1月12日
    0150
  • leetcode279-完全平方数

    原题 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出…

    2019年12月11日
    0150
  • leetcode700-二叉搜索树中的搜索

    原题 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。 例如, 给定二叉搜索树…

    算法 2020年1月16日
    0100

发表回复

登录后才能评论

评论列表(3条)