public class NextPermutation { public void nextPermutation(int[] num) { if (num == null) throw new NullPointerException("Null array!"); if (num.length == 0) return; int index = num.length - 1; while (index > 0 && num[index - 1] >= num[index]) { index--; } //if the whole array is in descending order, reverse the array and return if (index == 0) { reverse(num, 0, num.length - 1); return; } int pivot = --index; index = num.length - 1; while (num[index] <= num[pivot]) index--; swap(num, pivot, index); reverse(num, pivot + 1, num.length - 1); } private void swap(int[] num, int i, int j) { int tmp = num[i]; num[i] = num[j]; num[j] = tmp; } private void reverse(int[] num, int i, int j) { while (i < j) { swap(num, i, j); i++; j--; } } }
AdSense
Sunday, December 21, 2014
Next Permutation
This is much easier than the Permutation Sequence. Even though both of them are math problems. I follow the algorithm in this post. And I am stealing the graph from the post (thank you!).
Labels:
LeetCode
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment