凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 31. Next Permutation

分类:algorithm| 发布时间:2016-09-22 10:59:00


题目

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

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

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题意

给出一个数组求出这个数组的下一个排列。 不能申请额外的内存来交换数字,必须就地处理。

解法

我们使用数组 (0, 1, 2, 5, 3, 3, 0) 作为例子。

关键点在于,要求出下一个排列就要尽可能少地增加这个数组。 我们应该尽量修改靠右的数字,保持左边的数组不变。 比如,相比将第一个数字由 0 改为 1,将 (0, 1) 修改为 (0, 2) 更接近下一个排列。 当然,在这个例子中下一个排列不需要修改第二个数字。

首先,找出一个不能再增加的后缀。 在我们的例子中,这个后缀为 (5, 3, 3, 0)。 这个后缀已经是最高的排列了,所以我们不能只通过修改这个后缀来求出下一个排列——我们需要同时修改这个后缀左边的一个数字。

然后,将后缀左边的数字称为轴。 (如果没有这么一个数字,那么这个序列已经是最后一个排列方式。) 轴比后缀数组的第一个数字要小。因此后缀数组中至少有一个数字比轴要大。 如果我们将轴与后缀数组中比轴大的数字中的最小的一个交换,那么前缀数组就是最小的增加了。 (前缀数组为除后缀数组外的其他数字) 在本例中,我们得到了前缀数组 (0, 1, 3) 以及后缀数组 (5, 3, ,2, 0)

最后,将后缀数组按从小到大排序,因为我们增加了前缀数组,因此我们需要将后缀数组变得尽可能小。 其实我们可以反转后缀数组而不用将其排序,因为后缀数组本来就是按照从大到小排列的。 因此我们得到了下一个排列: (0, 1, 3, 0, 2, 3, 5)

用数学方法描述就是:

  • 找到最大的下标 i 使得 array[i - 1] < array[i]
  • 找到最大的下标 j 使得 j > i 并且 array[j] > array[i - 1]
  • 交换 array[j] 和 array[i - 1]
  • 反转 i 开始的后缀数组
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if (nums.empty()) return;

        // in reverse order, find the first number which is in increasing trend (we call it violated number here)
        int i;
        for (i = nums.size() - 2; i >= 0; --i) {
            if (nums[i] < nums[i+1]) break;
        }

        // reverse all the numbers after violated number
        reverse(begin(nums)+i+1, end(nums));
        // if violated number not found, because we have reversed the whole array, then we are done!
        if (i == -1) return;
        // else binary search find the first number larger than the violated number
        auto itr = upper_bound(begin(nums)+i+1, end(nums), nums[i]);
        // swap them, done!
        swap(nums[i], *itr);
    }
};

参考