|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | 3 | publicclass_31 { |
4 | | -publicstaticclassSolution1 { |
5 | | -/** |
6 | | - * Leetcode has a very good article to illustrate this problem and with animation: |
7 | | - * https://leetcode.com/articles/next-permutation/ |
8 | | - * 1. if the array is already in decrementing order, then there's no next larger permutation possible. |
9 | | - * 2. if not, start from the end of the array, find the first pair of numbers that break the decrementing order |
10 | | - * 3. then from that index going to the right again, find the element that is closest bigger than this number, swap them |
11 | | - * 4. reverse the right half of this array after this index |
12 | | - */ |
| 4 | +publicstaticclassSolution1 { |
| 5 | +/** |
| 6 | +* Leetcode has a very good article to illustrate this problem and with animation: |
| 7 | +* https://leetcode.com/articles/next-permutation/ |
| 8 | +* 1. if the array is already in decrementing order, then there's no next larger permutation possible. |
| 9 | +* 2. if not, start from the end of the array, find the first pair of numbers that break the decrementing order |
| 10 | +* 3. then from that index going to the right again, find the element that is closest bigger than this number, swap them |
| 11 | +* 4. reverse the right half of this array after this index |
| 12 | +*/ |
13 | 13 |
|
14 | | -publicvoidnextPermutation(int[]nums) { |
15 | | -inti =nums.length -2; |
16 | | -while (i >=0 &&nums[i] >=nums[i +1]) { |
17 | | -i--; |
18 | | - } |
19 | | -if (i >=0) { |
20 | | -intj =nums.length -1; |
21 | | -while (j >=0 &&nums[i] >=nums[j]) { |
22 | | -j--; |
23 | | - } |
| 14 | +publicvoidnextPermutation(int[]nums) { |
| 15 | +inti =nums.length -2; |
| 16 | +while (i >=0 &&nums[i] >=nums[i +1]) { |
| 17 | +i--; |
| 18 | +} |
| 19 | +if (i >=0) { |
| 20 | +intj =nums.length -1; |
| 21 | +while (j >=0 &&nums[i] >=nums[j]) { |
| 22 | +j--; |
| 23 | +} |
24 | 24 |
|
25 | | -swap(nums,i,j); |
26 | | - } |
| 25 | +swap(nums,i,j); |
| 26 | +} |
27 | 27 |
|
28 | | -reverse(nums,i +1); |
29 | | - } |
| 28 | +reverse(nums,i +1); |
| 29 | +} |
30 | 30 |
|
31 | | -privatevoidreverse(int[]nums,intstart) { |
32 | | -intend =nums.length -1; |
33 | | -while (start <=end) { |
34 | | -inttmp =nums[start]; |
35 | | -nums[start++] =nums[end]; |
36 | | -nums[end--] =tmp; |
37 | | - } |
38 | | - } |
| 31 | +privatevoidreverse(int[]nums,intstart) { |
| 32 | +intend =nums.length -1; |
| 33 | +while (start <=end) { |
| 34 | +inttmp =nums[start]; |
| 35 | +nums[start++] =nums[end]; |
| 36 | +nums[end--] =tmp; |
| 37 | +} |
| 38 | +} |
39 | 39 |
|
40 | | -privatevoidswap(int[]nums,inti,intj) { |
41 | | -inttmp =nums[i]; |
42 | | -nums[i] =nums[j]; |
43 | | -nums[j] =tmp; |
| 40 | +privatevoidswap(int[]nums,inti,intj) { |
| 41 | +inttmp =nums[i]; |
| 42 | +nums[i] =nums[j]; |
| 43 | +nums[j] =tmp; |
| 44 | + } |
44 | 45 | } |
45 | | - } |
46 | 46 | } |