递归不支持字典序,只支持全排列
1. 不含重复元素的全排列
/**
* <p>
* 求数组 a 从 a[start] 到 a[end] 的全排列
* 每次选中一个元素放在位置为 start 上，然后递归排列 a[start+1] a[end]
* 支持字典序（要求初始序列为字典序）
* 不支持重复元素
*/
public void recur2(int[] a, int start, int end) {
if (start == end) {
count2++;
System.out.println(Arrays.toString(a));
return;
}
for (int i = start; i <= end; i++) {
swap(a, i, start);
recur2(a, start + 1, end); // 递归排列
swap(a, i, start);
}
}
2. 含重复元素
public void recur3(int[] a, int start, int end) {
if (start == end) {
count3++;
System.out.println(Arrays.toString(a));
return;
}
HashSet<Integer> set = new HashSet<>();
for (int i = start; i <= end; i++) {
if (set.contains(a[i])) {
// 已经交换过值等于 a[i] 到 a[left] 的元素不再重复交换
continue;
}
set.add(a[i]); // 记录[start...right]中已经交换到a[left] 的元素
swap(a, i, start);
recur3(a, start + 1, end);
swap(a, i, start);
}
}
非递归处理
- 支持处理重复元素（不包含重复结果）
- 返回结果为字典序
public List<List<Integer>> permuteUnique2(int[] a) {
Arrays.sort(a);
List<List<Integer>> res = new ArrayList<>();
if (a == null || a.length == 0) return res;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < a.length; i++) list.add(a[i]);
res.add(list);
int j = a.length - 1;
while (true) {
j = a.length - 2;
while (j >= 0 && a[j] >= a[j + 1]) j--;
// 从右往左找到第一个a[j]< a[j+1]
if (j == -1) { // 说明当前a[] 顺序为降序, 全排列结束
break;
}
// 从[j+1,) 往后找大于 a[j]的最小值，与a[j] 交换
int minIndex = j + 1;
for (int k = minIndex + 1; k < a.length; k++) {
if (a[k] > a[j] && a[k] <= a[minIndex]) {
// = 必须要取，保证目标值有多个时，与 a[j] 交换的是最后一个值,使得交换后[j+1, ) 之后的数字仍然保持降序
minIndex = k;
}
}
swap(a, minIndex, j);
// [end,之后的所有元素是逆序，反转即可
reverse(a, j + 1, a.length - 1);
list = new ArrayList<>();
for (int i = 0; i < a.length; i++) list.add(a[i]);
res.add(list);
}
return res;
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
