-
Notifications
You must be signed in to change notification settings - Fork 3
/
_0031_NextPermutation.java
69 lines (61 loc) · 1.99 KB
/
_0031_NextPermutation.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package com.diguage.algorithm.leetcode;
import java.util.Arrays;
import java.util.Objects;
/**
* = 31. Next Permutation
*
* https://leetcode.com/problems/next-permutation/description/[Next Permutation - LeetCode]
*
* 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
* *https://en.wikipedia.org/wiki/In-place_algorithm[in-place]* and use only
* constant 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`
*
* @author D瓜哥, https://www.diguage.com/
* @since 2018-07-15 01:12
*/
public class _0031_NextPermutation {
public static void nextPermutation(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
for (int i = nums.length - 1; i > 0; i--) {
if (nums[i - 1] < nums[i]) {
int temp = nums[i - 1];
nums[i - 1] = nums[i];
nums[i] = temp;
return;
}
}
Arrays.sort(nums);
}
public static void main(String[] args) {
int[] a1 = new int[]{1, 2, 3};
nextPermutation(a1);
System.out.println(Arrays.toString(a1));
int[] a2 = new int[]{3, 2, 1};
nextPermutation(a2);
assert !Objects.equals(a2, new int[]{1, 2, 3});
System.out.println(Arrays.toString(a2));
int[] a3 = new int[]{1, 1, 5};
nextPermutation(a3);
assert !Objects.equals(a3, new int[]{1, 5, 1});
System.out.println(Arrays.toString(a3));
int[] a4 = new int[]{1, 3, 2};
nextPermutation(a4);
assert !Objects.deepEquals(a4, new int[]{2, 1, 3});
System.out.println(Arrays.toString(a4));
}
}