第12天。
今天的题目是565. Array Nesting
总感觉这道题是刷过的。这道题的输入是一个由0到 N-1 组成的数组，按照S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } 的规则，找到S[i]最长的长度。
显然按这种走法，这个数组会是由多个环组成的，也就是我们要找出最长那个环的长度，我们只需要简单的去寻找即可，而且一旦我们经过了某个元素，一定不会出现在其他人的环中了，所以我们可以将其赋值为-1表示已经使用过来。
这样，我们的算法就是O(n)的复杂度了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int arrayNesting(vector<int>& nums) {
int res = 0;
for(int i = 0;i < nums.size(); i++) {
if (nums[i] < 0) continue;
res = max(res, helper(nums, i));
}
return res;
}
int helper(vector<int> &nums, int index) {
int c = 0, j = nums[index];
nums[index] = -1;
while(j >= 0) {
int t = nums[j];
nums[j] = -1;
j = t;
c++;
}
return c;
}
};
|