luckydog

V1

2022/03/09阅读:39主题:默认主题

Code 31

数组

Code 31

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/next-permutation 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

代码

int i = nums.length - 2;
>
> ​    while (i >= 0 && nums[i] >= nums[i + 1]) {
>
> ​      i--;
>
> ​    }
>
> ​    if (i >= 0) {
>
> ​      int j = nums.length - 1;
>
> ​      while (j >= 0 && nums[j] <= nums[i]) {
>
> ​        j--;
>
> ​      }
>
> ​      swap(nums, i, j);
>
> ​    }
>
> ​    reverse(nums, i + 1);
>
>   }
>

>
>   public void reverse(int[] nums, int i) {
>
> ​    int left = i, right = nums.length - 1;
>
> ​    while (left < right) {
>
> ​      swap(nums, left, right);
>
> ​      left++;
>
> ​      right--;
>
> ​    }
>
>   }
>

>
>   public void swap(int[] nums, int i, int j) {
>
> ​    int tmp = nums[j];
>
> ​    nums[j] = nums[i];
>
> ​    nums[i] = tmp;
>
>   }

题解

本题关键在于发现从后向前遍历时候的升序 nums[i] >= nums[i + 1] (i begin from length - 2)此时得到的i为要被它之后序列中最小的那个数替换的

两数交换之后再对i之后的数字升序排列即可

分类:

后端

标签:

Java

作者介绍

luckydog
V1