AlgoPressAppearance
下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，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 <= 100 0 <= nums[i] <= 100
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/next-permutation 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
下一个排列，如果能够尽量固定前面的数，则调整后面的数可以得到结果 如果 1,2,3,4 我们固定住从后往前遍历，找到后面大于前面的数字，则后面的数字做出变更，前面的不需要变化。 后半部分变化，应该是选择比前面的大的数中最小的那个，和前面替换，比如 1,2,3, 7,6,5 我们找到7>3，所以从后面寻找比3大的数且是最小的那个。 因为后面的数到目前为止，是递增的，所以我们从后往前找到最小的那个和3进行替换 替换之后为 1,2,5, 6,7,3 此时我们还需要将剩下的数字排序获的最小值，即 1,2,5, 3,7,6
例外：如果我们一直遍历到开始都没有找到大于前面一个数字的索引，则说明现在全部降序排列，已经到最大值，则将所有数字都重新按需排列就得出最小值，为下一个排列。
参考代码
csharp
public class Solution {
public void NextPermutation(int[] nums) {
int n = nums.Length;
int index = n-1;
bool found = false;
while(index > 0){
//从后往前探索到有比自己小的数字，就停止
if(nums[index] > nums[index-1] ){
found = true;
break;
}
index--;
}
//如果一直没有找到，则说明已经到最后一个数字，则重新排列
if(!found){
index = 0;
}
Console.WriteLine("index = {0}",index);
//如果 index > 0 ，则和前面的那个数字交换
// 此处有问题，不能直接交换，而是拿出后面的数字中刚好大于前面的数字器交换
// 如 1 3 2 后面的数不是 3 1 2 而是 2 1 3
if(index > 0){
//从后面找出大于前面的数，且是最小的那个数，来替换
//因为此时后面的数字到index位置，都是自增的，所以我们从后往前查找即可
for(int j=n-1;j>=index;j--){
if(nums[j] > nums[index-1]){
Console.WriteLine("交换 {0} -- {1}",nums[index-1],nums[j]);
int temp = nums[index-1];
nums[index-1] = nums[j];
nums[j] = temp;
break; //替换一个成功后就退出循环
}
}
}
//因为大的数字放到前面去了，后面的数字按照顺序排列即为最小
// index --> end
sort(nums,index,n-1);
}
private void sort(int[] nums, int start, int end){
for(int i=start; i<=end-1; i++) {
for(int j=i+1;j<=end;j++){
if(nums[i] > nums[j]){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
}
}
参考代码2：优化上面的逻辑
我们其实就是要找到两个点 i 表示找到的第一个前面小于后面数的坐标。 j 表示后面的数大于 i 的坐标，然后将两个数去交换。 第三部，是剩下的 i+1 开始的数，其实也不是排序，而是反序，因为目前所有后面的数字都是倒序的，我们改成升序即可。
csharp
public class Solution {
public void NextPermutation(int[] nums) {
int i = nums.Length - 2;
//找到第一个降序的数（注意这里非增序的也到往前遍历)
while( i>=0 && nums[i] >= nums[i+1] ){
i--;
}
//再从后面找到大于i的数，如果i一直退回到开始，那么说明是-1，则后续不用处理
if(i>=0){
int j = nums.Length - 1;
while(j>i){
if(nums[j] > nums[i]){
break;
}
j--;
}
//交换i,j
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
//Console.WriteLine("i={0}",i);
//将 i+1 开始的数字反序
int left = i+1;
int right = nums.Length-1;
while(left < right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
}
复习代码：抽取公共函数
csharp
public class Solution {
public void NextPermutation(int[] nums) {
//找到第一个递减的数
int i=nums.Length-2;
while(i >= 0 && nums[i] >= nums[i+1]){
i--;
}
Console.WriteLine("i={0}",i);
//从i开始, 往后找一个最小的j大于i，从后往前找
if(i>=0){
int j = nums.Length - 1;
while(nums[j] <= nums[i]){
j--;
}
//交换
swap(nums,i,j);
}
//从i+1开始，排序后面的数字
reverse(nums,i+1);
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start){
int left = start;
int right = nums.Length - 1;
while(left < right){
swap(nums,left,right);
left++;
right--;
}
}
}
复习：20220704
- 第一步：从后往前找到第一个降序的位置，那个位置就是需要调整的地方
- 第二步：从后往前找到第一个大于降序位置的数，和它交换
- 第三步：从下一个位置开始，将数据前后交换反序
csharp
public class Solution {
public void NextPermutation(int[] nums) {
//从后往前找到第一个降序的地方
int n = nums.Length;
int index1 = -1;
int index2 = 0;
for(int i=n-2; i>=0; i--){
if(nums[i] < nums[i+1]){
index1 = i;
break;
}
}
if(index1 >=0 ){
//再从后面找到大于i的数
for(int i=n-1; i>=0; i--){
if(nums[i] > nums[index1]){
//将两个互换
int tmp = nums[i];
nums[i] = nums[index1];
nums[index1] = tmp;
//剩下的倒序
index2 = index1+1;
break;
}
}
}
Console.WriteLine("index1={0}",index1);
Console.WriteLine("index2={0}",index2);
//倒序剩下的数据，即为排序最小值
int j = index2, k = n-1;
while(j<k){
int tmp = nums[j];
nums[j] = nums[k];
nums[k] = tmp;
j++;
k--;
}
}
}