Got TLE on the first attempt as expected. I realized that my duplicate checking was using linear time each time, which was too slow.
This is where a data structure called map comes in handy.
After switching to map, it passed in 888ms.
I still need to study and practice map usage more. Here is the code:
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
| #include <map>
using namespace std;
class Solution {
public:
vector<vector<int>> ans;
map<vector<int>, int> markmap;
bool flag[100000];
int sum;
vector<vector<int>> permuteUnique(vector<int> &num) {
// Note: The Solution object is instantiated only once and is reused by each test case.
ans.clear();
markmap.clear();
sum = num.size();
for(int i = 0; i < sum; i++) {
flag[i] = false;
}
for(int i = 0; i < sum; i++) {
flag[i] = true;
vector<int> tmp(sum);
tmp[0] = i;
fun(tmp, 1, num);
flag[i] = false;
}
return ans;
}
void fun(vector<int> &tmp, int k, vector<int> &num) {
if(k >= sum) {
vector<int> numtmp(sum);
for(int i = 0; i < sum; i++) {
numtmp[i] = num[tmp[i]];
}
map<vector<int>, int>::iterator l_it = markmap.find(numtmp);
if(markmap.empty() || l_it == markmap.end()) {
ans.push_back(numtmp);
markmap[numtmp] = 590;
}
return;
}
for(int i = 0; i < sum; i++) {
if(!flag[i]) {
flag[i] = true;
tmp[k] = i;
fun(tmp, k + 1, num);
flag[i] = false;
}
}
}
};
|