整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
解题思路：排列 + 原地排序
● 首先来观察一波，1-4的排列：
(1) 1,2,[3],4
(2) 1,[2],4,3
(3) 1,3,[2],4
(4) 1,[3],4,2
……
● 分析下一个排列如何推出？
(1) 当前排列从右往左看每一个元素，如果发现排在它后面的元素存在比它大的，那么这个元素对应的位置就有增大的空间！
(2) 在(1)的基础上，对于那些排在后面且比当前元素大的数字来说，选择字典序中最小的那个和它交换。【贪心】
(3) 在(2)的基础上，交换后，将这个元素后面的数字从小到大排序。
以上面为例，说明如何推出：
(1)→(2)：4后面没有比它大的，3后面比它大的元素有4，所以3这个位置就可以设置为4，交换3、4
(2)→(3)：3后面没有比它大的，4后面没有比它大的，2后面比它大的元素有[3, 4]，下一个排列根据【贪心】的思想，我们选择3和它交换！那么交换后的排列为：1,3,4,2。此时可以保证3后面的数字无论怎么排序，这个排列都会比排列(2)要大，所以将3后面的元素贪心的从小到大排序即可。
(3)→(4)：4后面没有比它大的，2后面有比它大的元素4，元素2、4交换
不难推出：
(4)→(5)：2后面没有比它大的，4后面没有比它大的，3后面比它大的元素为4，交换3、4，此时排列为：1,4,3,2，将4后面的数字从小到大排序：1,4,2,3，这就是排列(5)。
……
⭕ 注意：题目说了，当没有下一个排列时，要求返回字典序第一个排列（即从小到大的的排列）
● 对于不能申请额外空间的【原地排序】，常用的有：冒泡排序、选择排序、堆排序。
（本题使用冒泡排序）
class Solution {
public void nextPermutation(int[] nums) {
// 1. 从右到左先找到应该开始变化的下标i，[0, i)不变
// 满足：存在i+1开始的元素，有比nums[i]更大的，且记录下第一个比它大的下标j
// 2. 如果i找到了，或者i<0:
// 2.1 i找到了：
// 2.1.1 nums[i]和nums[j]交换
// 2.1.2 对i+1之后的元素从小到大排序
// 2.2 i<0：对0之后的元素从小到大排序
// 找i的下标，以及后面第一个比nums[i]大的下标和值
int i = nums.length-1;
int largerinfo[] = findLargerValAndIndex(nums, i);
int largerVal = largerinfo[0];
int largerIndex = largerinfo[1];
while(largerIndex == -1){
i--;
if(i < 0) break;
largerinfo = findLargerValAndIndex(nums, i);
largerVal = largerinfo[0];
largerIndex = largerinfo[1];
}
// 两种情况讨论
if(i < 0) bubbleSort(nums, 0, nums.length-1);
else{
int tmp = nums[i];
nums[i] = nums[largerIndex];
nums[largerIndex] = tmp;
bubbleSort(nums, i+1, nums.length-1);
}
}
// 从下标l+1开始找nums数组中比nums[l]大，且最小的那个
public int[] findLargerValAndIndex(int[] nums, int l){
int curVal = -1;
int curIndex = -1;
for(int j=l+1; j<nums.length; j++){
if(nums[j] > nums[l] && (curIndex == -1 || nums[j] < curVal)){
curVal = nums[j];
curIndex = j;
}
}
return new int[]{curVal, curIndex};
}
// 冒泡从小到大排序
public void bubbleSort(int[] nums, int l, int r){
if(l < r){
for(int i=l; i<r; i++){ // 轮次
for(int j=l; j<r-i+l; j++){ // 判断nums[j]、nums[j+1]
if(nums[j] > nums[j+1]){ // 说明要交换
int tmp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tmp;
}
}
}
}
}
}
