|
| 1 | +packagemedium; |
| 2 | +/** |
| 3 | + * 31. Next Permutation |
| 4 | +
|
| 5 | +Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. |
| 6 | +
|
| 7 | +If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). |
| 8 | +
|
| 9 | +The replacement must be in-place, do not allocate extra memory. |
| 10 | +
|
| 11 | +Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. |
| 12 | +1,2,3 → 1,3,2 |
| 13 | +3,2,1 → 1,2,3 |
| 14 | +1,1,5 → 1,5,1*/ |
| 15 | +publicclassNextPermutation { |
| 16 | +/**Leetcode has a very good article to illustrate this problem and with animation: https://leetcode.com/articles/next-permutation/ |
| 17 | + * 1. if the array is already in decrementing order, then there's no next larger permutation possible. |
| 18 | + * 2. if not, start from the end of the array, find the first pair of numbers that break the decrementing order |
| 19 | + * 3. then from that index going to the right again, find the element that is closest bigger than this number, swap them |
| 20 | + * 4. reverse the right half of this array after this index*/ |
| 21 | + |
| 22 | +publicvoidnextPermutation(int[]nums) { |
| 23 | +inti =nums.length-2; |
| 24 | +while (i >=0 &&nums[i] >=nums[i+1]) { |
| 25 | +i--; |
| 26 | + } |
| 27 | +if (i >=0) { |
| 28 | +intj =nums.length-1; |
| 29 | +while (j >=0 &&nums[i] >=nums[j]) { |
| 30 | +j--; |
| 31 | + } |
| 32 | + |
| 33 | +swap(nums,i,j); |
| 34 | + } |
| 35 | + |
| 36 | +reverse(nums,i+1); |
| 37 | + } |
| 38 | + |
| 39 | +privatevoidreverse(int[]nums,intstart) { |
| 40 | +intend =nums.length-1; |
| 41 | +while (start <=end){ |
| 42 | +inttmp =nums[start]; |
| 43 | +nums[start++] =nums[end]; |
| 44 | +nums[end--] =tmp; |
| 45 | + } |
| 46 | + } |
| 47 | + |
| 48 | +privatevoidswap(int[]nums,inti,intj){ |
| 49 | +inttmp =nums[i]; |
| 50 | +nums[i] =nums[j]; |
| 51 | +nums[j] =tmp; |
| 52 | + } |
| 53 | + |
| 54 | +} |