Code & Fun

第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;
}
};

本文首发于Code & Fun