31. Next Permutation

LeetCode 31. Next Permutation****

Description

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

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

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

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

Input: nums = [1]
Output: [1]

Constraints:

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 100

Tags

Array

Solution

The basic idea is to find a permutation which is just larger than the current one but with the smallest possible gap.

We need to find the first two successive number nums[i] and nums[j] from the right, which satisfy nums[i] < nums[j]. If no such pair, what should we do is just reverse the whole array, because it has already been the last permutation and we need to rearrange it as the lowest possible order.

Now, nums[j:] is in descending order. We firstly find a position k where nums[k] > nums[i] from the right. Secondly, swap the both. Lastly, reverse the nums[j:] (which is still in descending order) to make the permutation as small as possible.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$

Code

func nextPermutation(nums []int) {
	i, j, k := len(nums)-2, len(nums)-1, len(nums)-1
	for i >= 0 && nums[i] >= nums[j] { // find the first ascending pair in inverted order
		i--
		j--
	}
	if i >= 0 { // if nums is not sorted in descending order
		for nums[i] >= nums[k] { // find the first k that nums[k] > nums[i] in inverted order
			k--
		}
		nums[i], nums[k] = nums[k], nums[i] // swap them
	}
	for i, j := j, len(nums)-1; i < j; i, j = i+1, j-1 { // reverse the remain descending part
		nums[i], nums[j] = nums[j], nums[i]
	}
}

Reference

1. 下一个排列算法详解：思路+推导+步骤，看不懂算我输！