permutationII ，如果不用hashset，用迭代的方法，如何防止重复 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

permutationII ，如果不用hashset，用迭代的方法，如何防止重复

permutationII ，如果不用hashset，用迭代的方法，如何防止重复# JobHunting - 待字闺中

R*92014-08-31 07:08

1 楼

说要使用12％得coupon，就要收回我得blackberry torch，赶紧忍气吞声结帐赶紧走人
。

y*i2014-08-31 07:08

2 楼

public static List> getPerms(int[] num) {
if (num == null || num.length == 0) {
return null;
}
List> res = new ArrayList>();
List first = new ArrayList();
res.add(first);
for (int i = 0; i < num.length; i++) {
List> newRes = new ArrayList>();
for (int j = 0; j < res.size(); j++) {
List current = res.get(j);
for (int k = 0; k <= current.size(); k++) {
List item = new ArrayList(current);
item.add(k, num[i]);
newRes.add(item);
}
}
res = newRes;
}
return res;
}
这个是permutation 1，在这基础上如何改？

w*r2014-08-31 07:08

3 楼

12%能用吗？求证一下

h*e2014-08-31 07:08

4 楼

class Solution {
public:
vector > permuteUnique(vector &num) {
vector > vec;
sort(num.begin(), num.end());
do
{ vec.push_back(num);
}while(next_permutation(num.begin(), num.end()));
return vec;
}
};
昨天写的　I/II 都好用.

c*y2014-08-31 07:08

5 楼

换家店试试？

【在 R****9 的大作中提到】

: 说要使用12％得coupon，就要收回我得blackberry torch，赶紧忍气吞声结帐赶紧走人
: 。

y*i2014-08-31 07:08

6 楼

大哥你这偷懒得厉害啊，直接用库函数了，面试肯定不让啊。

【在 h*******e 的大作中提到】

: class Solution {
: public:
: vector > permuteUnique(vector &num) {
: vector > vec;
: sort(num.begin(), num.end());
: do
: { vec.push_back(num);
: }while(next_permutation(num.begin(), num.end()));
: return vec;
: }

h*e2014-08-31 07:08

7 楼

next permutation leetcode 里面也有阿，二分搜一下，swap一下，然后 reverse一下。

【在 y***i 的大作中提到】

:
: 大哥你这偷懒得厉害啊，直接用库函数了，面试肯定不让啊。

y*i2014-08-31 07:08

8 楼

下。
能不能通过先排序的方法，具体怎么做想不出

【在 h*******e 的大作中提到】

: next permutation leetcode 里面也有阿，二分搜一下，swap一下，然后 reverse一下。