题目

image.png

思路

  • 题解
  • 第一点：我们应该经历操作低位的数而不应该操作高位的数
  • 第二点：从后往前找到第一个非升序的数m，这样就可以从后面那一个中取一个最小但是比m大的进行交换，确保交换的数比原来的大。
  • 第三点：由于m后面数从后往前看是升序的，直接反转就能得到最小的数据，但是又比原来大。

  • 最后需要注意判断全为降序情况，因此我们初始值要特殊处理为-1，方便判断这种情况，就不用进行第二步操作

    代码

    1. public void nextPermutation(int[] nums) {
    2.       if (nums.length == 0) return;
    3.       int index = -1; //置为-1是为了判断哪些刚好全部降序情况
    4.       //1.从后往前找到第一个非升序的m
    5.       for (int i = nums.length - 2; i >= 0; i--) {
    6.           if (nums[i] < nums[i + 1]) {
    7.               index = i;
    8.               break;
    9.           }
    10.       }
    11.       //2.从后往前找到第一个比m大的n，然后交换
    12.       for (int i = nums.length - 1; i >= 0 && index >= 0; i--) {
    13.           if (nums[i] > nums[index]) {
    14.               swap(i, index, nums);
    15.               break;
    16.           }
    17.       }
    18.       //3.将m位置后面的数反转
    19.       for (int i = index + 1, j = nums.length - 1; i < j; i++, j--) {
    20.           swap(i, j, nums);
    21.       }
    22.   }
    24.   private void swap(int i, int j, int[] nums) {
    25.       int t = nums[i];
    26.       nums[i] = nums[j];
    27.       nums[j] = t;
    28.   }

    下一个排列