leetcode #31 下一个排列 | 刷题之路第一站——数组类相关问题

【谁能想到我已经八天没有刷力扣了orz……】

题号 31

题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

链接：leetcode #31 下一个排列

解题思路【双指针？】：

思路来自：powcai 和万总
1- 最简单的一种情况：如果给定数的倒数第二位小于倒数第一位，则直接调换二者即可
例如：
1，2，3 —— 1，3，2
1，1，5 —— 1，5，1
2- 其他情况：
　（1）从后往前寻找第一个满足 nums[i] < nums[i+1] 的元素i，令第一个索引 firstIndex = i ；如果找不到这样的i，则将所有给定数进行翻转；
　例如：
　1，7，8，3，2 可以注意到后三位8，3，2是递增的，不可能在后三位中进行调换，因为无论哪两位交换，势必会比现在的数小，选择firstIndex指向从后往前第一个小于其后一个的元素
　1，8，7，3，2 同理：后四位8，7，3，2是递增的，也不可能在后四位中进行调换，所以firstIndex指向数字1
　所以这一步的目的就是找出来满足 nums[i] < nums[i+1] 的最大索引。
　（2）从后往前寻找第一个满足 nums[j] > nums[firstIndex] 的元素j，令第二个索引secondIndex = j;
　这一步的目的是找到 firstIndex 之后，比 nums[firstIndex] 大的最小元素，即secondIndex
　例如：
　1，7，8，3，2 firstIndex指向数字7，secondIndex指向数字8
　1，8，7，3，2 firstIndex指向数字1，secondIndex指向数字2
　（3）交换 nums[firstIndex] 和 nums[secondIndex]；
　nums[secondIndex] 是 firstIndex 之后大于nums[secondIndex]的最小的元素，二者交换可以保证使原有数字增大。
　例如：
　1，7，8，3，2 交换之后为：1，8，7，3，2
　1，8，7，3，2 交换之后为：2，8，7，3，2
　（4）将下标 firstIndex+1至最后一个元素进行翻转。
　观察可知，经过步骤3之后，原数字增大了，但增大幅度过多，只需将firstIndex后的各个数字变为升序排列即可。
　例如：
　1，8，7，3，2 翻转之后为：1，8，2，3，7 符合要求
　1，8，7，3，2 翻转之后为：2，1，3，7，8 符合要求

【备注：第一种情况也可以包含在第二种情况里，可以单独进行处理，也可以不处理】
　
时间复杂度： O(n)
空间复杂度： O(1)

代码实现：

class Solution {
public:
	void nextPermutation(vector<int>& nums) {
		if (nums.size() == 0) return;
		int firstIndex = -1;
		for (int i = nums.size() - 2; i >= 0; i--) {    //从后往前寻找第一个满足nums[i]<nums[i+1]的元素，即firstIndex
			if (nums[i] < nums[i + 1]) {
				firstIndex = i;
				break;
			}
		}
		if (firstIndex == -1) {    //如果找不到这样的元素，则将整个数组进行翻转即可
			reverse(nums.begin(), nums.end());
			return;
		}
		int secondIndex = -1;
		for (int i = nums.size() - 1; i >= 0; i--) {    //从后往前寻找第一个满足nums[i]>nums[firstIndex]的元素，即secondIndex
			if (nums[i] > nums[firstIndex]) {
				secondIndex = i;
				break;
			}
		}
		swap(nums[firstIndex], nums[secondIndex]);    //交换firstIndex和secondIndex
		reverse(nums.begin() + firstIndex + 1, nums.end());    //将fistIndex之后的元素进行翻转
		return;
	}
};