LeetCode 31 Next Permutation

本文主要是介绍LeetCode 31 Next Permutation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一串数字，求该排列的下一个排列。如果该排列为字典序最大排列，则输出字典序最小排列。

思路：

首先C++里面有求下一个排列的函数next_permutation，该函数返回0即表示当前排列字典序最大。

如果要自己动手实现，那么就考虑“如何找到比当前排列大1的排列”。

假设排列A（aaaXddd）比排列B（aaaYfff）大1，a部分为两排列相同部分，X与Y表示最靠左边不同的那一位。那么，X>Y且X一定在B中的f部分且f中数字一定是递减排序的且d一定是递增排序的。

代码：

class Solution {
public:void nextPermutation(vector<int> &nums) {int idx = findPos(nums);if (idx == -1) {reverse(nums.begin(), nums.end());} else {reverse(nums.begin() + idx + 1, nums.end());for (int i = idx + 1; i < nums.size(); ++i) {if (nums[idx] < nums[i]) {swap(nums[idx], nums[i]);break;}}}}private:int findPos(vector<int> &nums) {for (int i = nums.size() - 2; i >= 0; --i) {if (nums[i] < nums[i + 1]) {return i;}}return -1;}
};/*** 偷懒版本……*/class Solution {
public:void nextPermutation(vector<int> &nums) {if (!next_permutation(nums.begin(), nums.end())) {sort(nums.begin(), nums.end());}}
};

这篇关于LeetCode 31 Next Permutation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---