$$\color{Red}{下一个排列【leetcode31 找规律+二分】}$$
下面的链接是——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
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：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
解析
这题目，最开始我还以为需要用 dfs 找第一个全排列字典序比它大的元素，没有就返回最大字典序的情况。
后面看到题目要求只能使用常数空间，而且原地修改，那就说明只能是双指针或者是二分这种常数算法了。
仔细思考，观察题目的序列，可以发现，题目所说的下一个排列，是比当前排列字典序大，且是满足比它字典序大的所有全排列的最小情况。
[3, 4, 7, 4, 6, 1] - > [3, 4, 7, 6, 1, 4]
即让从后往前看【满足从后往前为递增的】 第一个 逆序的数被后面这个倒序递增【正序递减】序列中刚好比它大的数和它交换，而后面的数还得满足字典序最小，那就只能后面的数从小到大排列。
为什么满足从后往前第一个递增？
因为字典序的增大的排列，首先一定是让一个字典序大的数往前移，所以肯定不能选小的往前移【字典序反而降低了】，其次如果出现从后往前的数字中，出现第一个不满足递增的情况， 即出现 左边的数小于右边的，上面的案例就是 4 < 6 ， 那显然应该在后面找一个比 4 大
但是题目会出现重复元素，所以我们需要把这种边界考虑到。
【那也就是说找到第一个逆序数，找和它交换的数的时候不能相等，相等交换相当于没变化，后面的数再按字典序最小排，直接字典序反而降低了】
方法展开
我们可以从后往前使用指针 k 找 第一个 满足 nums[k - 1] > nums[k] 的情况，因为我们知道排列一定满足最大的数后面的数是从小到大排的，故我们这样的策略一定能找到出现倒序的第一个数 =》 nums[k - 1] 。【如果找不到说明整个排列完全满足从头到尾依次从大到小的情况，如 [5, 4, 3, 2, 1]，那就直接按题目要求，对数组从小到大排序】
如果找到了第一个满足 nums[k - 1] > nums[k] 的情况：
为了更形象，我们以实际案例来说明 ： 3 4 5 4 2 1 –> 3 5 1 2 4 4
此时第一个满足逆序的数应该是 4，按照我们上面的推演，它的下标为 k - 1
我们应该从 k -> nums.length - 1 下标范围找第一个比它大的数
【不能相等，如果相等即还是 4】
3 4 5 4 2 1 --------交换-------> 3 4 5 4 2 1 ------后面的数排序------> 3 4 1 2 4 5
【找到第一个逆序数，找和它交换的数的时候不能相等，相等交换相当于没变化，后面的数再按字典序最小排，直接字典序反而降低了】
应该是 5【下标 k】 和 4 【下标 k - 1】 交换，然后 【k -> nums.length - 1】进行排序
寻找这个数，因为满足后面的数是单调的，可以使用二分，当然也可以依次遍历
java
class Solution {
public void nextPermutation(int[] nums) {
int k = nums.length - 1;
while (k > 0 && nums[k - 1] >= nums[k]) k --;
if (k == 0) Arrays.sort(nums);
else {
int t = nums[k - 1];
int l = k, r = nums.length - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (nums[mid] >= t) l = mid;
else r = mid - 1;
}
int temp = nums[l];
nums[l] = t;
nums[k - 1] = temp;
Arrays.sort(nums, k, nums.length);
}
}
}
