LeetCode_31: Next Permutation

# 引言

题目链接：https://leetcode.com/problems/next-permutation/

# 题目大意

给出一个序列实现下一个排列, 它将数字重新排列成满足字典序的下一个更大的数字排列

如果下一个排列不可能(已经是最大的了), 则必须将其重新排列为尽可能低的顺序(即按升序排序)

• Example

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]求取下一个排列的步骤如下：

/*
 * 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
 */

步骤解读：

1. 从后向前查找第一个相邻元素对(i,j), 并且满足nums[i] < nums[j]。显然, 此时从j到end必然是降序。
2. 在[j,end)中寻找一个最小的k使其满足nums[i] < nums[k]。由于[j,end)是降序的, 所以必然存在一个k满足上面条件；并且可以从后向前查找第一个满足nums[i] < nums[k]关系的k, 此时的k必是待找的k。
3. 将i与k交换。此时, i处变成比i大的最小元素, 因为下一个全排列必须是与当前排列按照升序排序相邻的排列, 故选择最小的元素替代i, 交换后的[j,end)仍然满足降序排序。因为在(k,end)中必然小于i, 在[j,k)中必然大于k, 并且大于i。
4. 逆置[j,end),由于此时[j,end)是降序的, 故将其逆置, 最终获得下一个全排列。

Hint: 如果在步骤1找不到符合的相邻元素对, 即此时i=begin, 则说明当前[begin,end)为一个降序顺序, 即无下一个全排列, 按照题意直接将整个排列逆置成升序

# 复杂度

时间复杂度 O(n)

空间复杂度 O(1)

# AC代码

c++版本

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版本

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--
	}
}