很多人都觉得学习算法，并木有什么卵用，因为觉得生活上用不到。
然而开始学习编程的时候，学算法，到了高级工程师的时候，依然要学习算法。
因为工程师对时间和空间的衡量尤为重要。
这里教授的是一种逻辑的思想，才到编程技术。
将复杂的东西，讲得简单。
这个专栏的目标是写一个连高中生都能看明白的算法专栏。
如何还没法看懂就只能说，你还没到高中生水平了（just for a joke）
这期的题目是下一个排列。
输入一组数列，如下
1,2,3 -> 1,3,2
1,3,2 -> 2,1,3
2,1,3 -> 2,3,1
2,3,1 -> 3,1,2
3,1,2 -> 3,2,1
3,2,1 -> 1,2,3
输入1,2,3，即返回下一组排列刚好大于1,2,3的下一个排列
如果输入的，如3,2,1，已经是最大值，即返回最小值排列。
首先，这里需要先观察规律，可以多列几组数据，考究一下自身查找思考找到下一个最小值的过程。
1.是否有边界问题（也就是鲁棒性）
2.分解自身思考的过程，从前向后找，从后往前找。确定最大数，确定最小数。采取什么的方式确定最小值，思考。
下面是第一种解法的思路
输入初始排序的数组{
1.如果数组长度为1或者为0
直接返回数组
2.如果数组长度为2
直接交换数组中两个值的位置
返回交换后的数组
3.从最后一个值开始向前查找（循环1）
如果[这个值]比[前一个值]大（判断）
从最后往前查找截止到[这个值]（循环2）
如果出现有值大于[前一个值]（判断）
交换这两个值的位置
跳出循环2
遍历这个值的后一个值到末位（循环）
数字从两边分别交换数值，一直到中间
返回数组
4.排除前面三种情况，说明排序已经是从前往后是最大值
遍历从前到中间的位置(循环)
数字从两边分别交换数值，一直到中间
返回数组
}
这里最难想象的情况是第三种，我们以1,3,5,8,4,7,6,5,3,1这串数字来例子说明
1,3,5,8,4,7,6,5,3,1->1,3,5,8,5,7,6,4,3,1 从后往向前找，找到后数比前数大的情况，找到4比7小，这个确认值就为4，再重新从最后往前找，有第一个数（5）出现比这个确认值（4）大的情况，将这两个值交换。
交换确认值
1,3,5,8,5,7,6,4,3,1->1,3,5,8,5,1,3,4,6,7 然后把7,6,4,3,1倒序之后，就是下一个排列了
倒序数组
时间复杂度O(N平方)，空间复杂度是O(1)
输入初始排序的数组
vector<int> nextPermutation(vector<int> &nums) {
1.如果数组长度为1或者为0
if(nums.size() == 1 || nums.size() == 0)
直接返回数组
return nums;
2.如果数组长度为2
if(nums.size() == 2) {
直接交换数组中两个值的位置
swap(nums[0], nums[1]);
返回交换后的数组
return nums;
}
3.从最后一个值开始向前查找（循环1）
for(int i = nums.size() - 1; i > 0; i--) {
如果[这个值]比[前一个值]大（判断）
if(nums[i] > nums[i - 1]) {
从最后往前查找截止到[这个值]（循环2）
for(int j = nums.size() - 1; j >= i; j--)
如果出现有值大于[前一个值]（判断）
if(nums[j] > nums[i - 1]) {
交换这两个值的位置
swap(nums[i - 1], nums[j]);
跳出循环2
break;
}
遍历这个值的后一个值到末位（循环）
for(int j = 0; j < (nums.size() - i) / 2; j++)
数字从两边分别交换数值，一直到中间
swap(nums[i + j], nums[nums.size() - j - 1]);
return nums;
}
}
4.排除前面三种情况，说明排序已经是最大值
遍历从前到中间的位置(循环)
for(int j = 0; j < nums.size() / 2; j++)
数字从两边分别交换数值，一直到中间
swap(nums[j], nums[nums.size() - j - 1]);
返回数组
return nums;
}
是否有更优的解法呢？
第二种解法，时间O(N) 空间O(1)
关键在于将第三个阶段分解，将两个循环拆分，即可减少时间复杂度。
（1）从后往向前找，找到后数比前数大的情况，记住这个值，结束循环
（2）从最后往前找，在第一个出现比这个值大的情况，交换这两个值交换。
（3）将这个值之后的数组倒序排列，就是下一个排列了
public void nextPermutation(vector<int>& nums) {
i为数组倒数第二个值，j为倒数第一个值
int n = nums.size(), i = n - 2, j = n - 1;
找出倒数第二个值比倒数第一个值要小的时候，此时找到确认值（循环）
while (i >= 0 && nums[i] >= nums[i + 1])
下一个数
--i;
如果找到最后能找到需要交换的值
if (i >= 0) {
循环查找到确认值之后第一个大于确认值的的数（循环）
while (nums[j] <= nums[i])
--j;
交换确认值和这个数的位置
swap(nums[i], nums[j]);
}
倒序确认值之后的数组
reverse(nums.begin() + i + 1, nums.end());
}
可以看到没有循环叠加所以时间复杂度是O(n),时间复杂度为O(1)
附上LeetCode的Next Permutation位置
https://leetcode.com/problems/next-permutation/description/
网友评论