Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
public class NextPermutation{
public void nextPermutation(int[] num) {
if(num == null || num.length == 0) return;
int len = num.length;
if(len == 1) return;
int i = len - 2;
while(i >= 0 && num[i] >= num[i+1]) i--;
if(i >= 0){
int ceilingIndex = findCeiling(num, num[i], i+1, len-1);
swap(num, i, ceilingIndex);
}
// I used to sort this part. No need at all. They are always in descending order
// if they are not, we will not be at the current switch point.
reverse(num, i+1, len-1);
}
private int findCeiling(int[] num, int target, int low, int high){
int j = high;
while(j >= low && target >= num[j]) j--; // be sure to use >=
return j;
}
private void reverse(int[] num, int left, int right){
while(left <= right) swap(num, left++, right--);
}
private void swap(int[] num, int i, int j){
int tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment