31. Next Permutation

题目

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题意

题目说是要求出给定排序的数组的下一个更大的排列，重点是更大的，下一个。也就是例如115这个排列，下一个更大的就是151。再聚另外一个例子，127431，下一个更大的就是131247. 例如6 5 4 8 7 5 1，下一个就为65511478

题解

所以观察例子，我们发现，从后面往前面看，找到第一个不递增的元素，如127431，就是2这个元素，然后再从2后面的递增子数组中找出第一个比他大的元素进行交换，交换后卫137421，在将原来的位置往后的元素进行递增排序，既得131247。所得结果就是下一个更大的排列数组了

代码

import (
    "sort"
)

func nextPermutation(nums []int)  {
    Len := len(nums)
    if Len==1{
        return
    }
    //从后往前找第一个不是递增的元素
    pre := nums[Len-1]
    i:=0
    for i=Len-2;i>=0;i--{
        if nums[i]>=pre{
            pre = nums[i]
            continue
        }else{
            break
        }
    }
    
    //重新排序
    if i==-1{
        sort.Ints(nums)
        return
    }
    
    //交换位置
    swapIndex := i
    
    for i=Len-1;i>swapIndex;i--{
        if nums[i]<=nums[swapIndex]{
            continue
        }else{
            break
        }
    }
    
    temp:=nums[swapIndex]
    nums[swapIndex]=nums[i]
    nums[i]=temp
    
    //后面的进行递增排序
    sort.Ints(nums[swapIndex+1:])
    return
}

• ← Previous Post
• Next Post →