Permutaions II
给定一个数组, 返回数组中所有不重复的序列
my solutions (108 -> 24ms)
一开始我的想法是, 按照 46 题的解法, 然后用 set 自动去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| static const int _ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
return 0;
}();
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& v) {
size = v.size();
if (size == 1) return {v};
else if (size == 0) return {};
permuteUnique_do(v, 0);
return { ret.begin(), ret.end() };
}
private:
void permuteUnique_do(vector<int>& curv, int begin) {
if (begin >= size) {
ret.insert(ret.begin(), curv);
return;
}
for (int i = begin; i < size; ++i) {
swap(curv[i], curv[begin]);
permuteUnique_do(curv, begin + 1);
swap(curv[i], curv[begin]);
}
}
private:
set<vector<int>> ret;
size_t size;
};
|
但是这得到了 108 ms 的答案, 我思索了一下, 速度的瓶颈在于:
我对多个数做了同样的操作, 但最后将他们其中的大部分都抛弃了
要结局这种问题, 需要从源头入手, 在操作之前, 就将这些数据跳过
不过我暂时没有什么好的想法, 看了一下最好的答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| static const int _ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}();
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
do{
res.push_back(nums);
}while(next_permutation(nums.begin(), nums.end()));
res.erase(unique(res.begin(),res.end()),res.end());
return res;
}
};
|
emmm, 他又用了标准库
本来想着这道题就这样算了, 但是突然想到, 这好像和 31 题很类似…
然后我改良了一下算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| static const int _ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
return 0;
}();
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& v) {
size_t size = v.size();
if (size == 1) return {v};
else if (size == 0) return {};
sort( v.begin(), v.end() );
ret.push_back(v);
while ( nextPermutation(v) ) {
ret.push_back(v);
}
return ret;
}
private:
bool nextPermutation(vector<int>& nums) {
size_t size = nums.size();
for (int i = size - 1; i > 0; --i) {
if (nums[i] > nums[i - 1]) {
int i2 = nums[i - 1];
vector<int>::iterator it = nums.end();
while ( ++i2 < size ) {
if ( ( it = find(nums.begin() + i + 1, nums.end(), i2) ) != nums.end() )
break;
}
if ( it != nums.end() ) {
*it ^= nums[i - 1];
nums[i - 1] ^= *it;
*it ^= nums[i - 1];
} else {
nums[i] ^= nums[i - 1];
nums[i - 1] ^= nums[i];
nums[i] ^= nums[i - 1];
}
sort(nums.begin() + i, nums.end());
return true;
}
}
return false;
}
private:
vector<vector<int>> ret;
};
|
形状和 the best solution 类似, 但是过程我自己实现了, 换成了我在 31 题中的解法
最后, 我得到了仅次于最好答案的速度
(标准库还是没办法比得过的, 我什么时候能写出标准库一样漂亮的代码呢?)
(PS: 我是不是改抽一部分时间去分析一下标准库的东西?)
(一开始的 236 是我未将参数以引用传递)
(后面的 32 是我将 size 换成了类变量, 但是时间增加了, 看来对于经常访问的变量, 还是局部变量好)
(PS: 我不是分析过这些东西么, 为什么会犯这种错…)