|
|
|
|
|
|
a**********0 发帖数: 422 | 1 忘了哪个网友发过一个帖子 如果备选数字中有重复则不容易避免重复计数(在不使用
hashset一类的额外数据结构的时候)
我觉得可以这样 有个算法 是求下一个permutation 然后你从第一个permutation开始
生成 不断求下一个permutation 则此序列不会有重复
但是这个不是针对combination的 | a**********0 发帖数: 422 | 2 java代码
import java.util.*;
public class PermutationsII {
public ArrayList> permuteUnique(int[] num) {
Arrays.sort(num);
ArrayList> myResult = new ArrayList
Integer>>();
ArrayList temp1 = new ArrayList();
for(int i = 0; i<= num.length-1; i++)
temp1.add(num[i]);
myResult.add(temp1);
while(nextPermutation(num)){
ArrayList temp = new ArrayList();
for(int i = 0; i<= num.length-1; i++)
temp.add(num[i]);
myResult.add(temp);
}
return myResult;
}
public boolean nextPermutation(int[] num) {
int k = -1;
int l = -1;
int swap;
for(int i =0; i<= num.length-2; i++){
if(num[i]
k = i;
}
if(k == -1){
return false;
}
for(int i =k; i<= num.length-1; i++){
if(num[k]
l = i;
}
swap = num[k];
num[k] = num[l];
num[l] = swap;
for(int front = k+1, end = num.length-1; front < end; front ++, end-
-){
swap = num[front];
num[front] = num[end];
num[end] = swap;
}
return true;
}
}
【在 a**********0 的大作中提到】 : 忘了哪个网友发过一个帖子 如果备选数字中有重复则不容易避免重复计数(在不使用 : hashset一类的额外数据结构的时候) : 我觉得可以这样 有个算法 是求下一个permutation 然后你从第一个permutation开始 : 生成 不断求下一个permutation 则此序列不会有重复 : 但是这个不是针对combination的
|
|
|
|
|
|