leetcode 565. Array Nesting 最大的环的元素数量

╰半橙微兮° 2022-06-03 04:20 139阅读 0赞

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: 6  
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\].

本题题意有点绕，本质上就是就求环的元素的数量，直接暴力求解即可，注意使用标志数组来处理

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int arrayNesting(vector<int>& nums) 
        {
            int maxLen = 0;
            vector<bool> visit(nums.size(), false);
            for (int i = 0; i < nums.size(); i++)
            {
                if (visit[i] == false)
                {
                    int j = i, count = 0;
                    while (count == 0 || j != i)
                    {
                        visit[j] = true;
                        j = nums[j];
                        count++;
                    }
                    maxLen = max(maxLen,count);
                }
            }
    
            return maxLen;
        }
    };