[Link] https://leetcode.com/problems/next-permutation/
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
import java.util.Arrays;
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length, max = nums[len - 1];
if(len > 1) {
for(int i = nums.length - 2; i >= 0; i--) {
if(nums[i] < max) {
int insertIdx = findIdx(nums, i + 1, len - 1, nums[i]);
int temp = nums[insertIdx];
nums[insertIdx] = nums[i];
nums[i] = temp;
return;
} else if(nums[i] >= max) {
max = nums[i];
for(int j = i ; j < len - 1; j++) nums[j] = nums[j + 1];
nums[len - 1] = max;
}
}
}
}
int findIdx(int[] arr, int l, int r, int val) {
int mid;
while(l <= r) {
mid = (l + r) / 2;
if(arr[mid] <= val) l = mid + 1;
else if(arr[mid] == val) {
while(mid + 1 < arr.length && arr[++mid] == val);
return mid;
}
else r = mid - 1;
}
return l;
}
}