31. Next Permutation 下一个排列

题目

给定一个整数数组 nums，数组中元素为 0 ～ 100 。找到下一个整数数组的排列，使得这个排列比当前排列大。
[4,7,2,8,1,3] -> [4,7,2,8,3,1]
[7,6,5,8,9,3,2] -> [7,6,5,9,2,3,8]
[4,7,6,5,4,3] -> [5,3,4,4,6,7]
[7,6,5,4,9,7,4,3,2] -> [7,6,5,7,9,2,3,4,4]

解析

找到重排序的规律：
一个指针 flag 从 nums 尾部向头部移动，如果 nums[tail] < nums[tail-1]，对掉两个数的位置，做一次从小到大的排序。
特殊情况:
如果遍历到末尾我们还没有找到这样一个解，直接将整个数组反序列

1. 设置一个指针 指向倒数第二个数
2. 比较 flag 和 flag - 1 如果大于等于，步进
3. 如果小于，回溯回去，找到一个恰好比 flag 大的值，交换。记录 flag - 1
4. 坐标内的数是递减的，将其整个反向。

边界处理：
[1,3,2]
正向回溯时，如果最末尾的数仍然大于当前数，将最末尾的数和当前数做置换，例如 1 往后回溯，发现没有比 1 还小的数了，将末尾的数和 flag 对掉。

伪代码

for i = len-2;i >=0;i++
  if nums[i] < nums[i-1]
    for j:=i+2; i<len(num);j++
      if nums[j] <= nums[i]
          swap(nums[i], nums[j-1])
          break
  break
reverse(nums, i+1,len)

代码

func nextPermutation(nums []int)  {
    var i int
    for i=len(nums)-2; i>=0; i-- {
        if nums[i] < nums[i+1] {
            j := i+2
            for j < len(nums) && nums[j] > nums[i]{
                j++
            }
            swap(nums, i, j-1)
            break
        }
    }
    reverse(nums,i+1,len(nums)-1)
}

func reverse(nums []int, i int, j int) {
    for j>i {
        swap(nums, i ,j)
        i++
        j--
    }
}

func swap(nums []int, i int, j int) {
        nums[i] = nums[i] + nums[j]
        nums[j] = nums[i] - nums[j]
        nums[i] = nums[i] - nums[j]
}

image.png

image.png

同样的代码，两次效率不一样。