[LeetCode] 031. Next Permutation (Medium) (C++/Python)

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)Github: https://github.com/illuz/leetcode

031. Next Permutation (Medium)链接：

题目：https://oj.leetcode.com/problems/next-permutation/代码(github)：https://github.com/illuz/leetcode

题意：

求一个序列的下一个排列。

分析：

可以用 STL 里的 ‘next_permutation’ 偷懒。

具体算法是：

首先，，从最尾端开始往前寻找两个相邻的元素，令第一个元素是 i，第二个元素是 ii，且满足 i<ii ；然后，再从最尾端开始往前搜索，找出第一个大于 i 的元素，设其为 j；然后，将 i 和 j 对调，再将 ii 及其后面的所有元素反转。

代码：

C++:

class Solution {public:void nextPermutation(vector<int> &num) {if (!num.size())return;int idx = num.size() – 2;// 1. find out the last wrong orderwhile (idx >= 0 && num[idx] >= num[idx + 1])idx–;// 2. swapif (idx >= 0) {int i = idx + 1;while (i < num.size() && num[i] > num[idx])i++;swap(num[i – 1], num[idx]);}// 3. reversereverse(num.begin() + idx + 1, num.end());}};

Python:

class Solution:# @param num, a list of integer# @return nothing (void), do not return anything, modify num in-place instead.def nextPermutation(self, num):if not len(num):returnidx = len(num) – 2# 1. find out the last wrong orderwhile idx >= 0 and num[idx] >= num[idx + 1]:idx -= 1# 2. swapif idx >= 0:i = idx + 1while i < len(num) and num[i] > num[idx]:i += 1num[i – 1], num[idx] = num[idx], num[i – 1]# 3. reverseleft, right = idx + 1, len(num) – 1while left <= right:num[left], num[right] = num[right], num[left]left += 1right -= 1

把艰辛的劳作看作是生命的必然，