If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate 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
public class Solution { public void nextPermutation(int[] num) { // The following algorithm generates the next permutation lexicographically after a given permutation. // It changes the given permutation in-place. // 1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation. // 2. Find the largest index l greater than k such that a[k] < a[l]. // 3. Swap the value of a[k] with that of a[l]. // 4. Reverse the sequence from a[k + 1] up to and including the final element a[n-1]. int n = num.length; if (n <= 1) return; int k = -1; int l = -1; // Step 1 for (int i = n-2; i >= 0; i--) if (num[i] < num[i+1]) { k = i; break; } // If can't find k, num is the last permuation if (k == -1) { Arrays.sort(num); return; } // Step 2 for (int i = n-1; i > k; i--) if (num[i] > num[k]) { l = i; break; } // Step 3 swap(num, k, l); // Step 4 for (int i = k+1; i < (k+1)+(n-(k+1))/2; i++) swap(num, i, n+(k+1)-i-1); } private void swap(int[] num, int i, int j) { int temp = num[i]; num[i] = num[j]; num[j] = temp; } }
No comments:
Post a Comment