LeetCode做题记录————31下个一排列

唠唠

这一题为什么特地拿出来说，还是因为 4 月的时候师兄面试蔚来，被问到了这道算法题，当时师兄没答出来，然后回来和我们分享经验的时候聊到这题。

我心想这题我会啊，C++里直接使用 STL 算法库里的一个函数：next_permutation，但是师兄对 C++不太熟 orz，那么用算法怎么写呢？

我思考几秒后脱口而出：

你可以从后往前找，找到第一个对左小右大的组合，然后对调

那你怎么保证刚好是下一个呢

因为从后往前的话，你找到一定是可以替换的最低位的数字，这样就能保证你的这次替换是最小的

嗯.......好像确实有道理

嗯，就没有然后了，乍一看好像确实是这样，但是我在第一层 orz。

更气的是之后想起来我大二的时候在湖南工学院参加比赛的时候第一题就是这个，当时直接用 STL 的next_permutation。30 秒 A 了拿了一血 emmmm，谁知道让我自己写我竟然不能考虑全面，哎不说了，来看题吧

题面

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3]，一下都可以视作它的排列：[1,2,3]、[1,3,2]、[2,3,1]、[3,1,2]，

现在我们将一组数的全排列按十进制升序排列，当前排列的下一个排列指该排列在升序排列种的下一个排列。

例如，arr = [1,2,3]的下一个排列是[1,3,2]
类似的，arr = [2,3,1]的下一个排列是[3,1,2]
而对于arr = [3,2,1]，由于不存在比他更大的排列吗，它的下一个排列即升序排列的第一个[1,2,3]

现在给你一个整数数组nums，要求输出nums的下一个排列

要求控件复杂度为常数

数据符合如下条件：

1 <= nums.length <= 100
0 <= nums[i] <= 100

分析

首先题目要求空间复杂度为常数，意味着我们无法使用 DBF 或 BFS 这种需要借用额外数据结构的搜索算法进行搜索求解，因此我们只能通过交换原本数组种的某些位置得到所求字符串。

因此对于交换，我们需要满足以下条件：

比原数字大（在十进制下）
且是所有比原数字大大数种最小的（在十进制下）

那么首先想到的应该是把较大的数字放在尽量低的数位，例如：

对于1243，为了使其增大，我们需要将末尾处更大的数字回到更高的数位，但为了保证得到的数尽可能的小，我们会选择用 3 去和 2 交换，而不是 4，这样做是因为 3 比 4 要小，但我们怎么知道比 2 大一点点的数在哪里呢？

首先我们需要明确的是，我们需要让尽量低位的数字变大。然后再来思考这个问题，对于一组数 abcd。为了让可以和更大数字换的，尽量低位的数字变大，因此我们需要从末尾考试寻找，找到第一个可以更换的位置，假设该数位 b。

那么我们应该用哪个数字替换这个最低位可以替换的数字呢？我们可以试着写一下某个序列的全排列，例如 1234 的：

写着写着是不是有点头绪了？我们发现对于某个我们确定需要替换的位置，我们会尽量去找该位置后面的数字与之交换。需要证明的话，我们使用反证法也很好证明：

对于数字 b，我们假设 b 之前存在一个数字 x，可以与之交换，使得原数变得更大，那么我们交换 x 和 b，显然这一步使得我们的更高位（比 b 更高）遭到了变化，该变化显然没有用更大的数字与 b 交换跟小，因为我们相当于至少为该数字增加了（b-x）_ （length - Index_x - 1）_ 10 的大小。
如果使用 b 之后的数位 y 与之交换，那么我们将增加（y - b） _ (length - index_b - 1) _ 10 的大小，其中 y - b 和 b - x 均为 < 10 的数字，而 index_x 与 index_b 至少相差 1，那么即使 y-b = b-x，最终使用 x 替换后的增大量也要比使用 y 替换时大了 10 倍。
因此我们能确定需要使用 b 之后的数字替换。

那么问题又来了，是使用尽量靠近 b 的数字替换，还是尽量远离 b 的数字替换？我们在使用反证法：

对于 b，我们如果使用 d 去替换，显然是 ok 的，但是我们现在假设 b 和 d 之间存在那么一个 x，使得 b < x < d。那么显然使用 x 去替换 b 会得到更小的结果。
但是我们需要明确一点：x 在 b 之后。那么在这一情况下，我们使用 x 与 d 交换岂不是更优？这与b是第一个可以被替换的数字这一假设相矛盾。
因此我们知道寻找用于替换的数也要从后往前找。

于是我们可以得到1342。

好的，我第一遍听到这个题目的时候，思维就停留在了这里，以为这一问题得到了解答，但显然事情并不简单。

我们思考，这已经是最小的了吗？显然不是。虽然该数的百位被替换为了非常合适的 3，但这一位之后的数字呢？由于我们已经写出了 1234 的全排列，因此我们知道，1243 的下一个全排列是 1324，而不是 1342。

这是为什么呢，难道是我们分析的不对吗？

其实我们的分析是对的，毕竟通过严格的数学证明进行了论证，只是我们考虑的不够全面。我只保证了可以更换的第一位进行了最优的替换，但并没有保证该位置之后的数位保持最小！

我们知道，该位之后的子串也可以组成全排列，那么我们只需要保证这一全排列最小即可，即升序排列，因此我们还需要进行一步操作：对该位之后的数位进行排序。

最终我们得到答案：1324

代码

void nextPermutation(vector<int>& nums) {
        // auto k = nums.end() - 1;
    for (auto i = nums.end() - 1; i >= nums.begin(); i--)
    {
        for (auto j = nums.end() - 1; j != i; j--)
        {
            // cout << "第一位 " << *i << " 第二位 " << *j << endl;
            if (*i < *j)
            {
                // cout << *i << ' ' << *j << " 交换" << endl;
                swap(*i, *j);
                sort(i + 1, nums.end());
                return;
            }
        }
    }
    sort(nums.begin(), nums.end());
}