1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// @Title: 下一个排列 (Next Permutation)
// @Author: 15816537946@163.com
// @Date: 2020-06-25 07:15:36
// @Runtime: 0 ms
// @Memory: 3.4 MB
/*
 * @lc app=leetcode.cn id=31 lang=golang
 *
 * [31] 下一个排列
 *
 * https://leetcode-cn.com/problems/next-permutation/description/
 *
 * algorithms
 * Medium (31.90%)
 * Likes:    281
 * Dislikes: 0
 * Total Accepted:    24.6K
 * Total Submissions: 76.6K
 * Testcase Example:  '[1,2,3]'
 *
 * 实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 *
 * 如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
 *
 * 必须原地修改,只允许使用额外常数空间。
 *
 * 以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 *
 */

func nextPermutation(nums []int) {
	for i := len(nums) - 1; i > 0; i-- {
		if nums[i-1] < nums[i] {
			minLarger := i
			//TODO improve with binary search
			for j := i; j < len(nums); j++ {
				if nums[j] > nums[i-1] && nums[j] < nums[minLarger] {
					minLarger = j
				}
			}
			nums[i-1], nums[minLarger] = nums[minLarger], nums[i-1]
			sort.Ints(nums[i:])
			return
		}
	}
	sort.Ints(nums)
	return
}