Previous Permuation
给定一个整数数组来表示排列,找出其上一个排列。
样例
给出排列[1,3,2,3],其上一个排列是[1,2,3,3]
给出排列[1,2,3,4],其上一个排列是[4,3,2,1]
注意
排列中可能包含重复的整数
Solution
这里找上一个排列,仍然使用字典序算法,大致步骤如下:
- 从后往前寻找索引满足 a[k] > a[k + 1], 如果此条件不满足,则说明已遍历到最后一个。
- 从后往前遍历,找到第一个比a[k]小的数a[l], 即a[k] > a[l].
- 交换a[k]与a[l].
- 反转k + 1 ~ n之间的元素。
为何不从前往后呢?因为只有从后往前才能保证得到的是相邻的排列,可以举个实际例子自行分析。
Code
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) {
if (nums == null || nums.size() <= 1) {
return nums;
}
// step1: find nums[i] > nums[i + 1]
int i = 0;
for (i = nums.size() - 2; i >= 0; i--) {
if (nums.get(i) > nums.get(i + 1)) {
break;
} else if (i == 0) {
// reverse nums if reach minimum
reverse(nums, 0, nums.size() - 1);
return nums;
}
}
// step2: find nums[i] > nums[j]
int j = 0;
for (j = nums.size() - 1; j > i; j--) {
if (nums.get(i) > nums.get(j)) {
break;
}
}
// step3: swap betwenn nums[i] and nums[j]
Collections.swap(nums, i, j);
// step4: reverse between [i + 1, n - 1]
reverse(nums, i + 1, nums.size() - 1);
return nums;
}
private void reverse(List<Integer> nums, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
Collections.swap(nums, i, j);
}
}
}