全排列 java 实现

2021-06-22/2021-06-22
0 评论 105 浏览

 1public boolean nextPermutation(int[] nums) {
 2    int n = nums.length;
 3    int i = n - 2;
 4    // 找到倒数第一个前面比后面小的元素
 5    while (i >= 0 && nums[i] >= nums[i + 1]) {
 6        i--;
 7    }
 8    // 已经是最大排列,没有下一个全排列
 9    if (i < 0) {
10        return false;
11    }
12    // 从后往前找到第一个大于 nums[i] 的元素
13    int j = n - 1;
14    while (j >= 0 && nums[i] >= nums[j]) {
15        j--;
16    }
17    swap(nums, i, j);
18    reverse(nums, i + 1);
19    return true;
20}
21
22// 交换 数组 i j 位置
23public void swap(int[] arr, int i, int j) {
24    int temp = arr[i];
25    arr[i] = arr[j];
26    arr[j] = temp;
27}
28
29// 从 start 位置反转数组
30public void reverse(int[] arr, int start) {
31    int left = start, right = arr.length - 1;
32    while (left < right) {
33        swap(arr, left, right);
34        left++;
35        right--;
36    }
37}


标题:全排列 java 实现
作者:Rainsheep
地址:HTTPS://www.rainsheep.cn/articles/2021/06/22/1624331430103.html

评论
发表评论
       
       
取消