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/

发表评论

登录后才能评论