问题描述
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2]have the following unique permutations:
[1,1,2],[1,2,1], and[2,1,1].
问题分析
这题和上题类似,本想直接套用上题的代码再用set去重,但是直接超时了。
正确的做法是判断判断num[start]~num[end]直间有没有相同的值,有的话就不做交换递归了,直接下一个。
代码实现
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (num.length == 0) return result;
permuteSwap2(0, num.length - 1, num, result);
return result;
}
private void permuteSwap2(int start, int end, int[] num, ArrayList<ArrayList<Integer>> result) {
if (start == end) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < num.length; i++) {
list.add(num[i]);
}
result.add(list);
return;
} else {
for (int i = start; i <= end; i++) {
if (!findSame(num, start, i)) {
int temp = num[start];
num[start] = num[i];
num[i] = temp;
permuteSwap2(start + 1, end, num, result);
temp = num[start];
num[start] = num[i];
num[i] = temp;
}
}
}
}
private boolean findSame(int[] num, int start, int end) {
for (int i = start; i < end; i++) {
if (num[i] == num[end]) {
return true;
}
}
return false;
}
网友评论