乐趣区

关于golang:Leetcode专题数组31下一个排列

力扣链接:
https://leetcode-cn.com/probl…
解题思路:

  1. 第一次接触这个算法,没想到 C ++ 的 STL 库中就有 next_permutation 这个算法,用于计算下一个字典序列,这个算法自身也是十分精妙,没有其余额定的,记住这个算法就能够了
  2. 回归到题目自身,首先第一步就是从后往前遍历数组,找到第一个不为降序的数字,也就是对于下标 i < i + 1; 有 a[i] > a[i+1]; 将此数记为 a,此时 i +1 ~ n- 1 的数字均为降序
  3. 持续从后往前遍历,找到第一个大于 a[i] 的数字,记为 b
  4. 而后将 a 和 b 进行调换
  5. 从 a + 1 到 n 此时为降序,能够应用二分翻转翻转数组,使其成为升序(也能够间接排序)
// 解题思路
// 1、从后向前找到第一个非降序的数,即 i < i+1 && a[i] < a[i+1]
// 2、从后往前找到第一个大于 a[i] 的数 a[j]
// 3、替换 a[i] 和 a[j], 此时 i +1~n 肯定是降序的
// 4、将 i + 1 后的数字翻转排序
func nextPermutation(nums []int)  {n := len(nums)
    i := n - 2
    for i >= 0 && nums[i] >= nums[i+1] {i--}
    if i >= 0 {
        j := n-1
        for j >= 0 && nums[i] >= nums[j] {j--}
        nums[i], nums[j] = nums[j], nums[i]
    }
    reverse(nums[i+1:])
}

func reverse(nums []int) {for i, n := 0, len(nums); i < n / 2; i++ {nums[i], nums[n-1-i] = nums[n-1-i], nums[i]
    }
}
退出移动版