Given a list of integers, which denote a permutation.
Find the previous permutation in ascending order.
Have you met this question in a real interview?
Yes
Example
For
[1,3,2,3], the previous permutation is [1,2,3,3]
For
[1,2,3,4], the previous permutation is [4,3,2,1]
Note
The list may contains duplicate integers.
public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers that's previous permuation
*/
public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
// write your code
for(int i = nums.size() - 2; i >= 0; i--){
if(nums.get(i) > nums.get(i+1)){
int j = nums.size()-1;
for( ; j > i; j--){
if(nums.get(i) > nums.get(j)){
break;
}
}
int temp = nums.get(i);
nums.set(i, nums.get(j));
nums.set(j, temp);
reverse(nums, i+1, nums.size()-1);
return nums;
}
}
reverse(nums, 0, nums.size()-1);
return nums;
}
private void reverse(ArrayList<Integer> nums, int i, int j){
while(i < j){
int temp = nums.get(i);
nums.set(i, nums.get(j));
nums.set(j, temp);
i++;
j--;
}
}
}
next permutaion:
public class Solution {
/**
* @param nums: an array of integers
* @return: return nothing (void), do not return anything, modify nums in-place instead
*/
public int[] nextPermutation(int[] nums) {
// write your code here
for(int i = nums.length - 2; i >= 0; i--){
if(nums[i] < nums[i+1]){
int j = nums.length - 1;
for(;j > i; j--){
if(nums[i] < nums[j]){
break;
}
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
reverse(nums, i+1, nums.length-1);
return nums;
}
}
Arrays.sort(nums);
return nums;
}
private void reverse(int[] nums, int i, int j){
while(i < j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
}
}
No comments:
Post a Comment