Rearrange number into the lexicographically next greater permutation of numbers
e.g., 1,2,3 -> 1,3,2
e.g., 1,1,5 -> 1,5,1
e.g., 1,2->2,1
If such arrangement is not possible, it must rearrange it as the lowest possible order(i.e., sorted in ascending order)
e.g., 3,2,1-> 1,2,3
e.g., 2,7, 6,3 ,5,4,1 -> 2,7,6, 4 1,3,5
2. Implementation
Not possible case: number is in ascending order from backward, the solution is reverse it
e.g., 3,2,1
Possible case: number is not in ascending order from backward, the solution is record the one where first non ascending occur.
e.g., 1,2,3 -> first non ascending occur is in length-2
e.g., 1,1,5 -> first non ascending occur is in length-2
Q1: what to do after find out non-ascending index?
A1: find the least greater number to replace it
Q1: After replacing, your number become greater but is that the next smallest?
A1: Not yet. there is one part you can still optimize - Reverse the backward ascending part into forward ascending one.
Input:[1,3,2]
Output:[3,2,1]
Expected:[2,1,3]
Input:[1,2,3]
Output:[3,2,1]
Expected:[1,3,2]
Runtime Error Message:Line 124: java.lang.ArrayIndexOutOfBoundsException: -1
Last executed input:[1]
int nonAscendingIndex = nums.length -2;
while (nonAscendingIndex >=0 && nums[nonAscendingIndex] >= nums[nonAscendingIndex+1] ) {
nonAscendingIndex--;
}
int leastGreaterIndex = nonAscendingIndex+1;
int leastGreaterIndex = nonAscendingIndex+1;
while( leastGreaterIndex < nums.length && nums[leastGreaterIndex] > nums[nonAscendingIndex] )
{
leastGreaterIndex++;
}
leastGreaterIndex--;
// Time:O(n), Space:O(1) //Runtime Error Message: //Line 139: java.lang.ArrayIndexOutOfBoundsException: -1 //Last executed input: //[1,2] // Input: //[1,2] //Output: //[1,2] //Expected: //[2,1] public void nextPermutation(int[] nums) { // validate the input if ( nums == null || nums.length == 0 ) { return; } // NOTE :start from back int nonAscendingIndex = nums.length -2; while (nonAscendingIndex >=0 && nums[nonAscendingIndex] >= nums[nonAscendingIndex+1] ) { nonAscendingIndex--; } // NOTE: case all backward ascending will both end up i = -1 if ( nonAscendingIndex >= 0 ) { // [1,2,3] -> [1,3,2] not [3,1,2] int leastGreaterIndex = nonAscendingIndex+1; while( leastGreaterIndex < nums.length && nums[leastGreaterIndex] > nums[nonAscendingIndex] ) { leastGreaterIndex++; } leastGreaterIndex--; swap(nums, nonAscendingIndex,leastGreaterIndex); } // case1: backward in descending case // case2: only one element // case3: regular case, after swap reverse(nums,i+1, num.length-1); } public void swap(int[] nums, int l, int r) { //validate the input if ( nums == null || nums.length ==0 ) { return; } int temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; } public void reverse (int[] nums, int start , int end) { // validate the input if (nums == null || nums.length ==0 ) { return; } int l = start; int r = end; while (l < r) { int temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; l++; r--; } }3. Similar Ones (M) Permutations (H) Permutations II (M) Permutation Sequence (M) Palindrome Permutation II
No comments:
Post a Comment