首页 > 代码库 > LeetCode Next Permutation

LeetCode Next Permutation

2024-08-01 15:39:28   220人阅读

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, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

 

一个数列的全部组合，找出下一个组合。例如123，132，213，231，312，321，123.

从最后一个开始，找出相邻的第一个不是倒序的数，几下索引p，对p之后的元素找出刚刚比p大的，交换后，排序。

 1 public class Solution { 2     public void nextPermutation(int[] num) { 3         if (num.length<=1) return ; 4         int p=0; 5         int temp=0; 6         boolean flag=false; 7         for (int i = num.length-1; i >0 ; i--) { 8             if (num[i]>num[i-1]){ 9                 p=i-1;10                 break;11             }12         }13 14         for (int i = num.length-1; i >=p ; i--) {15             if (num[i]>num[p]){16                 flag=true;17                 temp=num[i];18                 num[i]=num[p];19                 num[p]=temp;20                 break;21             }22         }23         if (p==0&&flag==false)p=-1;24         Arrays.sort(num,p+1,num.length);25 26 27 28     }29 }

 

LeetCode Next Permutation


联系
我们