-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path565.cpp
39 lines (39 loc) · 879 Bytes
/
565.cpp
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
// beat96%+O1Space.cpp
class Solution {
public:
int arrayNesting(vector<int> &nums) {
int n = nums.size(), maxlen = 0;
for (int i = 0; i < n; ++i) {
int value = nums[i], pos = i, len = 0;
while (value != -1) {
nums[pos] = -1;
pos = value;
value = nums[value];
++len;
}
maxlen = max(maxlen, len);
if (maxlen > n / 2)
return maxlen;
}
return maxlen;
}
};
// hashset.cpp
class Solution2 {
public:
int arrayNesting(vector<int> &nums) {
unordered_set<int> hashset;
int len = 0, n = nums.size(), maxlen = 0;
for (int i = 0; i < n; ++i) {
int value = nums[i];
while (hashset.find(value) == hashset.end()) {
hashset.insert(value);
value = nums[value];
++len;
}
maxlen = max(maxlen, len);
len = 0;
}
return maxlen;
}
};