LeetCode刷题实战31：下一个排列-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做下一个排列，我们先来看题面：

https://leetcode-cn.com/problems/next-permutation/

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

题意

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

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

样例

一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题解

从数组最后一个元素开始扫描，寻找到nums[i] > nums[i - 1]的第一个i值。如果得到i值大于等于1，说明数组存在下一个排列。

a.我们还是从数组最后一个元素开始扫描，寻找到num[j] > nums[i - 1]的第一个j值。由于nums[i] > nums[i - 1]，所以我们的j值一定是大于等于i的

b.交换索引为i - 1和索引为j的元素的值。

c.此时索引i及之后的排列时一个降序排列，将其变成升序排列即可。

为什么说此时索引i及之后的排列是一个降序排列呢？

对于原来的数组，由于我们是从数组最后一个元素开始扫描寻找到的nums[i] > nums[i - 1]的第一个i值，我们原数组中i之后的排列一定是一个降序排列。那么我们只需要看交换之后是否依然是一个降序排列呢？

而寻找索引j，我们还是从数组最后一个元素开始扫描，寻找到num[j] > nums[i - 1]的第一个j值。对于索引j之后的值，一定是小于等于nums[i - 1]的。对于而对于索引i到j - 1这部分元素，一定是大于等于num[j]的，自然一定大于nums[i - 1]，那么，交换之后，原数组中i之后的排列一定依然是一个降序排列。

（3）如果得到的i值小于1，说明数组不存在下一个排列，倒序输出数组即得升序排列。

public class Solution {
 
  public void nextPermutation(int[] nums) {
    int n = nums.length;
    int i = n - 1;
    for(; i >= 1; i--) {
      if(nums[i] > nums[i - 1]) {
        break;
      }
    }
    if(i >= 1) {
      int j = n - 1;
      for(; j >= i; j--) {
        if(nums[j] > nums[i - 1]) {
          break;
        }
      }
      swap(i - 1, j, nums);
      reverse(nums, i);
    }else {
      reverse(nums, 0);
    }
  }
  
  private void reverse(int[] nums, int index) {
    int i = index;
    int j = nums.length - 1;
    while(i < j) {
      swap(i, j, nums);
      i++;
      j--;
    }
  }
 
  private void swap(int i, int j, int[] nums) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}