引言
题目链接：https://leetcode.com/problems/next-permutation/
题目大意
给出一个序列实现下一个排列，它将数字重新排列成满足字典序的下一个更大的数字排列
如果下一个排列不可能（已经是最大的了），则必须将其重新排列为尽可能低的顺序（即按升序排序）
- Example
|
1 2 3 |
1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 |
题解
此题其实求解下一个全排列
假设集合nums当前全排列情况为 [3, 7, 6, 2, 5, 4, 3, 1]求取下一个排列的步骤如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
/* * current: 3 7 6 2 5 4 3 1 . * | | | | * find i----+ j k +----end * swap i and k : * 3 7 6 3 5 4 2 1 . * | | | | * i----+ j k +----end * reverse j to end : * 3 7 6 3 1 2 4 5 . * | | | | * find i----+ j k +----end */ |
步骤解读：
- 从后向前查找第一个相邻元素对(i,j)，并且满足nums[i] < nums[j]。显然，此时从j到end必然是降序。
- 在[j,end)中寻找一个最小的k使其满足nums[i] < nums[k]。由于[j,end)是降序的，所以必然存在一个k满足上面条件；并且可以从后向前查找第一个满足nums[i] < nums[k]关系的k，此时的k必是待找的k。
- 将i与k交换。此时，i处变成比i大的最小元素，因为下一个全排列必须是与当前排列按照升序排序相邻的排列，故选择最小的元素替代i，交换后的[j,end)仍然满足降序排序。因为在(k,end)中必然小于i，在[j,k)中必然大于k，并且大于i。
- 逆置[j,end),由于此时[j,end)是降序的，故将其逆置，最终获得下一个全排列。
Hint：如果在步骤1找不到符合的相邻元素对，即此时i=begin，则说明当前[begin,end)为一个降序顺序，即无下一个全排列，按照题意直接将整个排列逆置成升序
复杂度
时间复杂度 O(n)
空间复杂度 O(1)
AC代码
c++版本
|
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 |
class Solution { public: void nextPermutation(vector<int> &nums) { if (nums.size() <= 1) { return; } vector<int>::iterator iter_i = nums.end() - 1; vector<int>::iterator iter_j; vector<int>::iterator iter_k; while (iter_i != nums.begin()) { iter_j = iter_i--; if (*iter_i < *iter_j) { iter_k = nums.end(); while (!(*iter_i < *--iter_k)) ; iter_swap(iter_i, iter_k); reverse(iter_j, nums.end()); return; } } reverse(nums.begin(), nums.end()); } }; |
go版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
func nextPermutation(nums []int) { lens := len(nums) if lens <= 1 { return } i := lens - 1 for i > 0 && nums[i] <= nums[i-1] { i-- } if i > 0 { j := lens - 1 for nums[j] <= nums[i-1] { j-- } nums[i-1], nums[j] = nums[j], nums[i-1] } j := lens - 1 for i < j { nums[i], nums[j] = nums[j], nums[i] i++ j-- } } |
