C ++中的数组嵌套

假设我们有一个长度为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