Medium
面經(jīng)題
很直觀的思路观挎。找next permutation先找哪里可以下手，也就是從后到前數(shù)第一個(gè)nums[j-1] < nums[j]的地方，比如1243 找到2那里贡蓖，next permutation就是1324. 找到2的index也就是代碼里的first. 然后再找2后面最小的數(shù)這里是3，把它跟2交換煌茬，再把3后面的sort一下就好斥铺。注意一下edge case，比如第一次求first求出來(lái)是-1坛善， 那說(shuō)明整個(gè)已經(jīng)最大了晾蜘，都是降序，那返回一個(gè)最低排列就是正常升序就好了眠屎。
class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1){
return;
}
int first = -1;
for (int i = nums.length - 1; i > 0; i--){
if (nums[i-1] < nums[i]){
first = i-1;
break;
}
}
if (first == -1){
Arrays.sort(nums);
return;
}
int nextMin = Integer.MAX_VALUE;
int nextMinIndex = -1;
for (int j = first + 1; j < nums.length; j++){
if (nums[j] <= nums[first]){
continue;
}
if (nums[j] < nextMin){
nextMin = nums[j];
nextMinIndex = j;
}
}
swap(nums, first, nextMinIndex);
Arrays.sort(nums, first+1, nums.length);
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
