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

	}

}