题目描述
A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], … } subjected to the rule below.
Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.
Example 1:
Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
Note:
- N is an integer within the range [1, 20,000].
- The elements of A are all distinct.
- Each element of A is an integer within the range [0, N-1].
题意:索引从0开始长度为N
的数组A
,包含0到N - 1
的所有整数。找到并返回最大的集合S
,S[i] = {A[i], A[A[i]], A[A[A[i]]], … }
且遵守以下的规则。
假设选择索引为i
的元素A[i]
为S
的第一个元素,S
的下一个元素应该是A[A[i]]
,之后是A[A[A[i]]]...
以此类推,不断添加直到S
出现重复的元素。
算法1
(并查集) $O(n)$
题解1:并查集。我们可以知道对于任意的i
,i
和nums[i]
肯定是在同一个集合当中的,所以我们可以使用并查集来合并所有的元素。最终找到一个最大的连通分量。
class Solution {
public:
vector<int> fa,size;
int getfa(int x)
{
if(fa[x] != x)
fa[x] = getfa(fa[x]);
return fa[x];
}
void uni(int x,int y)
{
int fx = getfa(x),fy = getfa(y);
if(fx != fy)
{
if(size[fx] < size[fy])
{
fa[fx] = fy;
size[fy] += size[fx];
}else{
fa[fy] = fx;
size[fx] += size[fy];
}
}
}
int arrayNesting(vector<int>& nums) {
int n = nums.size(),res = 0;
fa = vector<int>(n);
size = vector<int>(n,1);
for(int i = 0 ; i < n ; i ++) fa[i] = i;
for(int i = 0 ; i < n ; i ++)
uni(i,nums[i]);
for(int i = 0 ; i < n ; i ++)
if(getfa(i) == i)
res = max(res,size[i]);
return res;
}
};
算法2
(标记数组) $O(n)$
题解2:遍历法,我们从i = 0
开始遍历,将i
不断的置成nums[i]
,直至再次i = 0
,这时候我们找到了所有的和0在一个集合中的元素,我们使用visit标记数组来标记哪些数字已经被遍历过了。再不断置换过程中如果遇到了已经遍历过的数字,说明当前集合已经被遍历完全了。
int arrayNesting(vector<int>& nums) {
int n = nums.size(),res = 0;
vector<bool> visit(n,false);
for(int i = 0 ; i < n ; i ++)
{
if(visit[i]) continue;
visit[i] = true;
int cur = 1,idx = nums[i];
while(visit[idx] == false)
{
visit[idx] = true;
idx = nums[idx];
cur ++;
}
res = max(res,cur);
}
return res;
}
算法3
(原地标记) $O(n)$
题解3:不使用额外空间。我们可以将遍历过的数字置成负数,起到visit的作用。
int n = nums.size(),res = 0;
for(int i = 0 ; i < n ; i ++)
{
if(nums[i] < 0) continue;
int cur = 1,idx = nums[i];
nums[i] = -1;
while(nums[idx] >= 0)
{
int pre = idx;
idx = nums[idx];
nums[pre] = -1;
cur ++;
}
res = max(res,cur);
}
return res;
}