C ++中的数组嵌套

  • Z时代
  • 2024-01-10
  • 分类：综合

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

以上是 C ++中的数组嵌套 的全部内容， 来源链接： utcz.com/z/322330.html

回到顶部