假设我们有一个长度为N的零索引数组A,其中包含从0到N-1的所有整数。我们必须找到并返回集合S的最长长度,其中S [i] = {A [i],A [A [i]],A [A [A [i []]],...}以下规则。现在考虑S中的第一个元素以索引= i的元素A [i]的选择开始,S中的下一个元素应为A [A [i]],然后是A [A [A [i]]]…以此类推,我们在S中出现重复元素之前就停止添加。因此,如果数组像A = [5,4,0,3,1,6,2],那么输出将为4,即A [ 0] = 5,A [1] = 4,A [2] = 0,A [3] = 3,A [4] = 1,A [5] = 6,最后A [6] = 2。
为了解决这个问题,我们将遵循以下步骤-
因此,创建一个称为dfs的函数。这将需要节点,arr数组,v数组和一组访问。在dfs数组中执行以下操作-
如果访问了节点,则返回
将节点插入v,将节点标记为已访问
dfs(arr [node],arr,v,已访问)
从主要方法中,执行以下操作-
ret:= 0,n:= nums的大小。制作一组称为Visited
对于i,范围为0至n – 1
创建一个数组v
如果未访问nums [i],则dfs(nums [i],nums,v,已访问)
ret:= ret的最大值和v的大小
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class Solution { public: void dfs(int node, vector <int>& arr, vector <int>& v, set <int>& visited){ if(visited.count(node)) return; v.push_back(node); visited.insert(node); dfs(arr[node], arr, v, visited); } int arrayNesting(vector<int>& nums) { int ret = 0; int n = nums.size(); set <int> visited; for(int i = 0; i < n; i++){ vector <int> v; if(!visited.count(nums[i]))dfs(nums[i], nums, v, visited); ret = max(ret, (int)v.size()); } return ret; } }; main(){ vector<int> v = {5,4,0,3,1,6,2}; Solution ob; cout << (ob.arrayNesting(v)); }
[5,4,0,3,1,6,2]
输出结果
4